기술면접 — 이진탐색트리, 힙

What(정의)와 WHY(왜)를 중심으로 공부하기 — 알고리즘(5)

이진 탐색트리

출처: https://medium.com/@konduruharish

WHAT

• 이진: 모든 노드가 둘 이하의 자식을 갖는
• 탐색: 정렬된 트리
  → 노드의 왼쪽 서브트리에는 그 노드의 값보다 작은 값들을 지닌 노드들
  → 노드의 오른쪽 서브트리에는 그 노드의 값보다 큰 값들을 지닌 노드들
• 트리: 트리구조

WHY

• 빠른 탐색: 탐색 시 시간 복잡도가 O(logN)
  → 1억개의 아이템에서 27번만에 원하는 값 찾음
  → 100개의 아이템에서 7번만에 원하는 값 찾음
• 삽입 할 때 시간복잡도 역시 O(logN)

주의

• 이진 탐색 트리의 균형이 깨지면, 탐색 시 시간 복잡도가 O(logN)이 아니라 O(N)에 근접한 시간이 소요될 수 있다.

힙

출처: https://medium.com/@konduruharish

WHAT

힙의 특성을 만족하는 거의 완전한 트리인 특수한 트리 구조

• 힙의 특성: 최소 힙에서는 부모가 항상 자식보다 작거나 같다.
• 완전 이진트리: 마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있으며, 마지막 레벨의 모든 노드는 가능한 한 가장 왼쪽에 있다. 마지막 레벨 h 에서 1부터 2h-1 개의 노드를 가질 수 있다.

WHY

• 최소 힙은 부모가 항상 자식보다 작기 때문에, 루트가 결국 가장 작은 값을 갖게 되며, 우선순위 큐에서 가장 작은 값을 추출하는 것은 매번 힙의 루트를 가져오는 형태로 구현된다. O(1) → 대신 삽입할 때마다 정렬해야 하므로, 삽입할 때의 시간복잡도는 O(NlogN)이다.
• 우선순위 큐
• 다익스트라 알고리즘에서도 힙을 사용하면 시간복잡도를 O(V²)에서 O(ElogV)로 줄일 수 있다.

주의

• 힙은 정렬된 구조가 아니다. 최소 힙의 경우 부모 노드가 항상 작다는 조건만 만족할 뿐, 서로 정렬되어 있지 않다.

이진탐색 트리와의 차이점

• 힙은 상/하 관계를 보장하고
• 이진 탐색 트리는 좌/우 관계를 보장한다.