[자료구조] Heap과 BST의 차이점

Heap은 상하관계를 보장하는 반면, BST는 좌우관계를 보장한다.

 

Heap

• Heap에서는 상위 level에 존재하는 값이 하위 level에 존재하는 값보다 우선순위가 높다.
• 하지만 좌/우에서의 우선순위는 절대적이지 않다.
• 왼쪽의 값이 우선순위가 높을수도, 오른쪽의 값이 우선순위가 높을수도 있다.
• Heap에서는 root가 가장 우선순위가 높기 때문에 가장 작은 값을 추출하거나 가장 큰 값을 추출해야 하는 경우 사용한다.

 

BST

• BST에서는 왼쪽의 값이 오른쪽의 값보다 작다.
• 하지만 상/하에서의 값은 절대적이지 않다.
• 상위 level에 존재하는 값이 하위 level에 존재하는 값보다 클수도, 작을수도 있다.
• BST는 (평균적으로) 탐색이 O(log n), 삽입/삭제가 O(log n)에 가능하기 때문에 탐색이 빈번하게 일어나는 경우 사용한다.

binary search tree