출시·고도화 중
트리와 힙 안내서 · 1/6
배열과 연결 리스트는 데이터를 한 줄로 늘어놓습니다. 그런데 폴더 안의 폴더, 회사 조직도, HTML 문서의 태그처럼 계층을 이루는 데이터는 한 줄로 표현하기 어렵습니다. 이런 데이터를 담는 구조가 트리(tree) 입니다. 트리를 조금 제한하면 정렬된 데이터를 빠르게 찾는 이진 탐색 트리가 되고, 다른 방향으로 제한하면 가장 작은 값(또는 가장 큰 값)을 빠르게 꺼내는 힙(heap) 이 됩니다. 이 장에서는 이 세 가지를 이해하는 데 필요한 용어와 직관을 정리합니다.
트리는 노드(node) 와 노드를 잇는 간선(edge) 으로 이루어지며, 다음 성질을 가집니다.
그래프 관점에서 보면 트리는 "사이클이 없는 연결 그래프"이고, 그중 한 노드를 루트로 정한 것이 우리가 다루는 루트 있는 트리입니다.
| 용어 | 뜻 |
|---|---|
| 부모 · 자식 | 간선으로 바로 이어진 위 · 아래 노드 |
| 형제 | 부모가 같은 노드들 |
| 잎(리프) | 자식이 없는 노드 |
| 내부 노드 | 자식이 하나 이상 있는 노드 |
| 깊이 | 루트에서 그 노드까지 간선 수(루트의 깊이는 0) |
| 높이 | 그 노드에서 가장 먼 잎까지 간선 수(잎의 높이는 0) |
| 서브트리 | 한 노드와 그 아래 자손 전체 |
| 차수 | 한 노드가 가진 자식 수 |
트리의 높이는 루트의 높이를 말합니다. 노드가 하나뿐인 트리는 높이가 0이고, 빈 트리는 관례상 -1로 둡니다. 교재에 따라 높이를 노드 수로 세는 경우도 있으니 문제를 풀 때 정의를 먼저 확인합니다.
모든 노드의 자식이 많아야 두 개(왼쪽 · 오른쪽)인 트리를 이진 트리라고 합니다. 자주 등장하는 모양은 다음과 같습니다.
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인지 확인할 때는 허용 범위를 함께 내려보냅니다.
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)) # TrueBST의 탐색 · 삽입 · 삭제는 트리 높이 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)입니다.
트리는 루트에서 하나의 경로로 모든 노드에 닿는 계층 구조입니다. 이진 탐색 트리는 "왼쪽은 작고 오른쪽은 크다"는 규칙으로 탐색을 빠르게 하며, 높이를 낮게 유지하는 것이 성능의 핵심입니다. 힙은 완전 이진 트리 모양과 부모-자식 순서만 지키는 구조로, 배열에 담아 우선순위 큐를 효율적으로 구현합니다.
댓글 0개
로그인 · 로그인하면 댓글을 남길 수 있습니다.
첫 댓글을 남겨 보세요.