개념 정리
트리와 이진 탐색 트리 (BST)
단원 개요
계층적 비선형 자료구조인 트리의 구조와 이진 트리 3대 순회(전위·중위·후위), 이진 탐색 트리(BST)의 원리, 힙(Heap)과 균형 트리(B-Tree)를 학습합니다.선수 개념
필수 키워드:트리(Tree)의 핵심 특징개루트(Root)리프(Leaf / 단말 노드)이진 트리 (Binary Tree): 왼쪽 서브트리 ➔➔ 오른쪽 서브트리 순으로 방문 (: 왼쪽 서브트리 ➔ 오른쪽 서브트리 ➔BST의 불변 규칙탐색·삽입·삭제 원리와 시간 복잡도
1
트리의 기본 성질과 이진 트리 3대 순회(Traversal)
•
트리(Tree)의 핵심 특징: 사이클(Cycle)이 없는 연결 그래프로, 개의 노드를 가진 트리의 간선(Edge) 수는 항상 개입니다. 최상단 노드를 루트(Root), 자식이 없는 말단 노드를 리프(Leaf / 단말 노드)라고 합니다.
•
이진 트리 (Binary Tree): 모든 노드의 자식이 최대 2개(왼쪽 자식, 오른쪽 자식) 이하인 트리입니다. 높이가 인 포화 이진 트리의 전체 노드 수는 개(루트 레벨을 1로 둘 때)입니다.
•
이진 트리 깊이 우선 순회 3가지 (현재 노드 를 언제 방문하는지로 구분):
1
전위 순회 (Pre-order: ): 루트(자신)를 먼저 방문한 뒤 왼쪽 서브트리 ➔ 오른쪽 서브트리 순으로 방문 (폴더 구조 복사, 전위 표기식).
2
중위 순회 (In-order: ): 왼쪽 서브트리 ➔ 루트(자신) ➔ 오른쪽 서브트리 순으로 방문 (이진 탐색 트리에서 오름차순 정렬 결과 출력!).
3
후위 순회 (Post-order: ): 왼쪽 서브트리 ➔ 오른쪽 서브트리 ➔ 루트(자신)를 마지막에 방문 (하위 폴더 용량 합산, 안전한 트리 메모리 해제).
핵심 원리
순회 이름의 '전(Pre)·중(In)·후(Post)'는 왼쪽(L)과 오른쪽(R)의 순서가 아니라(L은 항상 R보다 먼저!), '부모(Root) 노드를 언제 방문하느냐(맨 앞 / 가운데 / 맨 뒤)'를 뜻합니다.2
이진 탐색 트리 (Binary Search Tree, BST)와 편향 트리 문제
•
BST의 불변 규칙: 트리 내의 모든 노드 에 대하여 다음 대소 관계가 엄격히 성립합니다:
•
탐색·삽입·삭제 원리와 시간 복잡도:
•
찾고자 하는 값을 현재 노드와 비교하여 작으면 왼쪽으로, 크면 오른쪽으로 내려가므로 매 단계마다 탐색 대상이 절반으로 줄어듭니다.
•
평균(균형 잡힌 경우): 트리의 높이가 이므로 탐색·삽입·삭제 모두 에 수행됩니다.
•
최악(편향 트리, Skewed Tree): 만약 정렬된 데이터
[10, 20, 30, 40, 50]을 순서대로 BST에 삽입하면 오른쪽으로만 길게 늘어선 일자형 사슬(사실상 연결 리스트)이 되어 높이가 이 되고, 시간 복잡도가 으로 급격히 악화됩니다.풀이
1) 트리 구조 형성:
•
루트는 50입니다.
•
50의 왼쪽 자식은 30(그 자식으로 왼쪽 20, 오른쪽 40)이 배치됩니다.
•
50의 오른쪽 자식은 70(그 자식으로 왼쪽 60, 오른쪽 80)이 배치됩니다.
2) 전위 순회 (Root → L → R):
50 ➔ 30 ➔ 20 ➔ 40 ➔ 70 ➔ 60 ➔ 80
3) 중위 순회 (L → Root → R):
20 ➔ 30 ➔ 40 ➔ 50 ➔ 60 ➔ 70 ➔ 80 (정확히 오름차순으로 정렬됨!)
4) 후위 순회 (L → R → Root):
20 ➔ 40 ➔ 30 ➔ 60 ➔ 80 ➔ 70 ➔ 50 (루트 50이 가장 마지막에 출력됨)
3
자가 균형 트리(AVL, Red-Black), 힙(Heap), 데이터베이스 B-Tree
•
자가 균형 이진 탐색 트리 (Self-Balancing BST):
•
편향 트리로 퇴화하는 것을 막기 위해 삽입·삭제 시 노드 회전(Rotation)을 통해 스스로 높이를 으로 유지하는 트리입니다 (예: AVL 트리, C++
std::map과 Java TreeMap, 리눅스 스케줄러에 쓰이는 Red-Black 트리).•
힙 (Heap) vs 이진 탐색 트리 (BST) 구분:
•
힙(Heap)은 완전 이진 트리로서 부모 노드가 자식 노드보다 항상 크거나(최대 힙) 작기만(최소 힙) 하면 되며, 왼쪽 자식과 오른쪽 자식 사이의 대소 관계는 없습니다. 최댓값/최솟값을 에 확인하고 에 추출하는 우선순위 큐 구현에 특화되어 있습니다.
•
데이터베이스 인덱스의 심장, B-Tree / B+Tree:
•
디스크(SSD/HDD)에서 데이터를 읽을 때는 트리 높이를 극도로 낮춰야 디스크 I/O 횟수가 줄어듭니다. 따라서 DB 인덱스는 자식 노드를 2개가 아니라 수백 개씩 거느리는 다진 균형 탐색 트리인 B+Tree를 사용하여 수억 건의 데이터도 단 3~4번의 탐색으로 찾아냅니다.
주의할 점
흔히 하는 오해: '힙(Heap)과 이진 탐색 트리(BST)는 같은 것 아닌가?' -> 전혀 다릅니다! BST는 전체 데이터의 정렬 및 임의 값 검색(O(log N))을 위한 구조이고, 힙은 오직 가장 큰 값(Max)이나 가장 작은 값(Min)을 빠르게 꺼내기 위해 부모-자식 간 대소만 유지하는 완전 이진 트리입니다.핵심 요약
- ✓이진 트리의 전위(VLR)·중위(LVR)·후위(LRV) 순회는 부모 노드(V)의 방문 시점에 따라 구분된다.
- ✓이진 탐색 트리(BST)는 '왼쪽 자식 < 부모 < 오른쪽 자식' 규칙을 따르며, 중위 순회 시 오름차순 정렬 결과가 나온다.
- ✓BST는 평균 O(log N) 성능을 내지만 한쪽으로 치우친 편향 트리에서는 O(N)으로 저하되므로 Red-Black 트리 등 균형 트리가 필요하다.
- ✓힙(Heap)은 우선순위 큐 구현에 쓰이며, B+Tree는 디스크 접근 횟수를 최소화하기 위해 데이터베이스 인덱스에 사용된다.