트리 자료구조를 공부하다 보니 이진 트리(Binary Tree), 힙(Heap), 이진 탐색 트리(BST), 우선순위 큐(Priority Queue) 등의 개념이 서로 얽혀 있어 혼란스러웠습니다.
각 개념의 관계를 정리하면 트리를 더 잘 이해하는 데 도움이 될 것 같아, 이번 기회에 깔끔하게 정리해 보았습니다.
1. 이진 트리 (Binary Tree)
개념
- 각 노드는 최대 두 개의 자식 노드를 가질 수 있는 트리 구조입니다.
- 이진 트리는 단순한 자료구조이며, 정렬 방식이나 데이터 접근 규칙이 따로 정해져 있지 않습니다.
- 노드 개수는 최대 2^h - 1 개입니다. (h는 트리의 높이)
특징
- 탐색 규칙이 없는 단순한 구조적 개념입니다.
- 왼쪽, 오른쪽 자식을 가지는 트리 형태일 뿐입니다.
예시
A
/ \
B C
/ \ \
D E F2. 이진 탐색 트리 (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)으로 보장합니다.
반응형
