배열과 연결 리스트는 데이터를 한 줄로 늘어놓습니다. 그런데 폴더 안의 폴더, 회사 조직도, HTML 문서의 태그처럼 계층을 이루는 데이터는 한 줄로 표현하기 어렵습니다. 이런 데이터를 담는 구조가 트리(tree) 입니다. 트리를 조금 제한하면 정렬된 데이터를 빠르게 찾는 이진 탐색 트리가 되고, 다른 방향으로 제한하면 가장 작은 값(또는 가장 큰 값)을 빠르게 꺼내는 힙(heap) 이 됩니다. 이 장에서는 이 세 가지를 이해하는 데 필요한 용어와 직관을 정리합니다.
트리란 무엇인가
트리는 노드(node) 와 노드를 잇는 간선(edge) 으로 이루어지며, 다음 성질을 가집니다.
- 맨 위에 루트(root) 노드가 하나 있습니다.
- 루트를 뺀 모든 노드는 부모가 정확히 하나입니다.
- 사이클이 없습니다. 그래서 루트에서 어떤 노드로 가는 경로는 하나뿐입니다.
- 노드가 n개이면 간선은 항상 n - 1개입니다.
그래프 관점에서 보면 트리는 "사이클이 없는 연결 그래프"이고, 그중 한 노드를 루트로 정한 것이 우리가 다루는 루트 있는 트리입니다.
꼭 알아야 할 용어
트리의 높이는 루트의 높이를 말합니다. 노드가 하나뿐인 트리는 높이가 0이고, 빈 트리는 관례상 -1로 둡니다. 교재에 따라 높이를 노드 수로 세는 경우도 있으니 문제를 풀 때 정의를 먼저 확인합니다.
이진 트리
모든 노드의 자식이 많아야 두 개(왼쪽 · 오른쪽)인 트리를 이진 트리라고 합니다. 자주 등장하는 모양은 다음과 같습니다.
- 정 이진 트리(full): 모든 노드의 자식이 0개 또는 2개입니다.
- 포화 이진 트리(perfect): 모든 잎의 깊이가 같고 내부 노드는 자식이 2개입니다. 높이가 h이면 노드는 2^(h+1) - 1개입니다.
- 완전 이진 트리(complete): 마지막 레벨을 빼면 꽉 차 있고, 마지막 레벨은 왼쪽부터 채워집니다. 힙이 바로 이 모양입니다.
- 편향 트리(degenerate): 모든 노드가 자식을 하나만 가져 사실상 연결 리스트가 된 트리입니다.
Python에서는 노드를 작은 클래스로 표현합니다.
class Node:
def __init__(self, key, left=None, right=None):
self.key = key
self.left = left
self.right = right
def height(node):
if node is None:
return -1
return 1 + max(height(node.left), height(node.right))
def size(node):
if node is None:
return 0
return 1 + size(node.left) + size(node.right)
# 8
# / \
# 3 10
# / \ \
# 1 6 14
root = Node(8, Node(3, Node(1), Node(6)), Node(10, None, Node(14)))
print(height(root), size(root)) # 2 6
이진 탐색 트리(BST)
이진 탐색 트리는 모든 노드에서 "왼쪽 서브트리의 키는 모두 더 작고, 오른쪽 서브트리의 키는 모두 더 크다"는 규칙을 지키는 이진 트리입니다. 이 규칙 덕분에 루트에서 출발해 비교 한 번마다 한쪽 서브트리를 통째로 버릴 수 있어, 정렬된 배열의 이진 탐색과 같은 효과를 냅니다. 또 중위 순회(왼쪽, 자신, 오른쪽)를 하면 키가 오름차순으로 나옵니다.
규칙은 바로 아래 자식만이 아니라 서브트리 전체에 적용된다는 점이 중요합니다. 그래서 BST인지 확인할 때는 허용 범위를 함께 내려보냅니다.
def is_bst(node, low=float("-inf"), high=float("inf")):
if node is None:
return True
if not (low < node.key < high):
return False
return is_bst(node.left, low, node.key) and is_bst(node.right, node.key, high)
print(is_bst(root)) # True
균형이 왜 중요한가
BST의 탐색 · 삽입 · 삭제는 트리 높이 h에 비례합니다. 키가 고르게 퍼져 있으면 h는 약 log2 n이지만, 1, 2, 3, ...처럼 정렬된 순서로 넣으면 편향 트리가 되어 h = n - 1이 됩니다. 이를 막기 위해 삽입 · 삭제 때 회전(rotation)으로 모양을 고치는 자가 균형 트리를 씁니다. 대표적인 것이 각 노드의 좌우 높이 차를 1 이하로 유지하는 AVL 트리와, 노드에 빨강 · 검정 색을 매겨 가장 긴 경로가 가장 짧은 경로의 두 배를 넘지 않게 하는 레드-블랙 트리입니다. 이 안내서에서는 원리만 소개하고, 실무에서는 언어가 제공하는 구현을 씁니다.
힙과 우선순위 큐
이진 힙은 두 조건을 만족하는 이진 트리입니다. 첫째, 모양이 완전 이진 트리입니다. 둘째, 최소 힙이라면 모든 부모가 자식보다 작거나 같습니다(최대 힙은 반대). 그래서 루트에는 항상 최솟값이 있지만, 형제 사이나 서로 다른 서브트리 사이에는 순서가 없습니다. BST처럼 "정렬"된 것이 아니라 "가장 작은 것만 확실한" 구조입니다.
완전 이진 트리는 빈틈이 없으므로 포인터 없이 배열 하나에 레벨 순서로 담을 수 있습니다.
def parent(i):
return (i - 1) // 2
def left(i):
return 2 * i + 1
def right(i):
return 2 * i + 2
heap = [1, 3, 2, 7, 4, 5] # 최소 힙
for i in range(1, len(heap)):
assert heap[parent(i)] <= heap[i]
print(heap[0], left(1), right(1)) # 1 3 4
힙은 우선순위 큐를 구현하는 가장 흔한 방법입니다. 우선순위 큐는 "값 넣기"와 "가장 우선순위가 높은 값 꺼내기"를 지원하는 추상 자료형이고, 힙으로 구현하면 두 연산이 모두 O(log n)입니다.
무엇을 언제 쓰나
- 계층 데이터를 표현할 때: 일반 트리(파일 시스템, DOM, 구문 트리).
- 정렬 순서를 유지하며 찾기 · 범위 질의 · 이전 · 다음 값이 필요할 때: 균형 BST.
- 가장 작은(큰) 값만 반복해서 꺼내면 될 때: 힙과 우선순위 큐.
- 키로 찾기만 하면 될 때: 해시 테이블이 보통 더 빠릅니다.
정리
트리는 루트에서 하나의 경로로 모든 노드에 닿는 계층 구조입니다. 이진 탐색 트리는 "왼쪽은 작고 오른쪽은 크다"는 규칙으로 탐색을 빠르게 하며, 높이를 낮게 유지하는 것이 성능의 핵심입니다. 힙은 완전 이진 트리 모양과 부모-자식 순서만 지키는 구조로, 배열에 담아 우선순위 큐를 효율적으로 구현합니다.
댓글 0개
로그인 · 로그인하면 댓글을 남길 수 있습니다.