Computer Science/Data Structure

[DataStructure/Tree] 우선순위 큐, 힙, 이진 탐색 트리의 개념과 차이점 정리

quessr 2025. 2. 12. 10:14

 

트리 자료구조를 공부하다 보니 이진 트리(Binary Tree), 힙(Heap), 이진 탐색 트리(BST), 우선순위 큐(Priority Queue) 등의 개념이 서로 얽혀 있어 혼란스러웠습니다.
각 개념의 관계를 정리하면 트리를 더 잘 이해하는 데 도움이 될 것 같아, 이번 기회에 깔끔하게 정리해 보았습니다.

1. 이진 트리 (Binary Tree)

개념

  • 각 노드는 최대 두 개의 자식 노드를 가질 수 있는 트리 구조입니다.
  • 이진 트리는 단순한 자료구조이며, 정렬 방식이나 데이터 접근 규칙이 따로 정해져 있지 않습니다.
  • 노드 개수는 최대 2^h - 1 개입니다. (h는 트리의 높이)

특징

  • 탐색 규칙이 없는 단순한 구조적 개념입니다.
  • 왼쪽, 오른쪽 자식을 가지는 트리 형태일 뿐입니다.

예시

        A
       / \
      B   C
     / \   \
    D   E   F

2. 이진 탐색 트리 (Binary Search Tree, BST)

개념

  • 이진 탐색 트리는 이진 트리에 탐색 규칙을 추가한 구조입니다.
  • 왼쪽 서브트리에는 현재 노드보다 작은 값,
    오른쪽 서브트리에는 현재 노드보다 큰 값이 위치합니다.
  • 이진 탐색(BST) 규칙을 적용한 트리이므로 탐색이 빠릅니다. (O(log N))

특징

  • 탐색, 삽입, 삭제 연산의 시간 복잡도는 O(log N)입니다. (균형이 맞을 경우)
  • 이진 탐색이 가능하도록 정렬된 형태를 유지합니다.
  • 일반적으로 중복 값을 허용하지 않습니다.

예시

       8
      /  \
     4   10
    / \     \
   2   6    12

 

  • 탐색: 6을 찾고 싶다면 8 → 4 → 6 순서로 O(log N)에 탐색할 수 있습니다.
  • 삽입: 새로운 값을 넣을 때 BST 규칙을 유지하면서 적절한 위치에 삽입합니다.

3. 힙 (Heap)

개념

  • 힙은 완전 이진 트리(Complete Binary Tree) 형태를 유지합니다.
  • 부모-자식 간 특정한 우선순위를 유지하는 특수한 트리 구조입니다.
  • 이진 탐색 트리(BST)와는 다르게, 탐색보다는 우선순위 유지가 목적입니다.
    • 최대 힙(Max Heap): 부모 ≥ 자식
    • 최소 힙(Min Heap): 부모 ≤ 자식

특징

  • 탐색보다는 "우선순위 유지"가 중요한 자료구조입니다.
  • 우선순위 큐(Priority Queue)의 기반이 되는 자료구조입니다.
  • 힙 정렬(Heap Sort)의 기반이 됩니다.
  • 루트 노드는 항상 최소 또는 최대값을 가집니다.

예시 (최대 힙)

        100
       /   \
     50     30
    /  \   /  \
  20   10 5    3

 

 

  • 100이 항상 최상위(root)에 위치합니다.
  • 삭제 시, 가장 큰 값(100)이 제거됩니다.
  • 이후 힙 속성을 유지하도록 조정(Heapify)됩니다.

4. 우선순위 큐 (Priority Queue)

개념

  • 일반적인 큐(Queue)는 FIFO(First-In, First-Out) 방식으로 동작합니다.
  • 하지만 우선순위 큐는 "우선순위"가 높은 요소가 먼저 나오는 자료구조입니다.
  • 우선순위 큐는 일반적으로 힙(Heap) 자료구조를 기반으로 구현됩니다.
    • 최소 힙(Min Heap): 값이 작은 요소가 먼저 나옵니다.
    • 최대 힙(Max Heap): 값이 큰 요소가 먼저 나옵니다.

특징

  • 힙(Heap)을 사용하면 삽입 및 삭제 연산이 O(log N)으로 효율적입니다.
  • 힙을 사용하지 않고 정렬된 리스트나 이진 탐색 트리(BST)를 사용하여 구현할 수도 있지만,
    일반적으로 힙이 가장 효율적입니다.

예시 (최소 힙을 사용한 우선순위 큐)

val pq = PriorityQueue<Int>()  // 기본적으로 최소 힙 기반
pq.add(50)
pq.add(20)
pq.add(100)
pq.add(10)

while (pq.isNotEmpty()) {
    println(pq.poll())  // 우선순위가 높은(가장 작은) 값부터 출력
}

 

 

출력 결과:

10
20
50
100

 

(작은 값이 먼저 출력됨 = 최소 힙 기반)

개념 관계 정리

                자료구조 개념도
──────────────────────────────────────────────
    ┌─────────────────────────────┐
    │          트리 (Tree)         │
    └─────────────────────────────┘
                 │
    ┌─────────────────────────────┐
    │     이진 트리 (Binary Tree)  │
    └─────────────────────────────┘
                 │
   ┌────────────┴───────────────┐
   │                            │
┌──────────────┐          ┌──────────────────────┐
│   힙 (Heap)  │          │ 이진 탐색 트리 (BST) │
└──────────────┘          └──────────────────────┘
        │                              │
┌──────────────┐          ┌──────────────────────────┐
│  우선순위 큐 │          │ 균형 BST (AVL, Red-Black) │
│ (Priority Queue) │      └──────────────────────────┘
└──────────────┘

마무리 정리

  • 우선순위 큐는 힙을 기반으로 구현하는 것이 일반적입니다.
  • 힙은 완전 이진 트리를 기반으로 우선순위를 유지하는 구조입니다.
  • 이진 탐색 트리(BST)는 탐색을 빠르게 하기 위해 정렬된 트리 구조입니다.
  • 균형 BST(AVL, Red-Black Tree)는 BST의 균형을 유지하여 탐색을 O(log N)으로 보장합니다.
반응형