§ 1 · 둘을 가리키는 노드이진 트리란
연결 리스트의 노드는 다른 한 노드만 가리켰다. 트리(tree)의 노드는 여러 노드를 가리킬 수 있다. 그중 이진 트리(binary tree)는 다음 규칙을 따른다.
① 각 노드는 자식을 0개, 1개, 또는 2개 가진다.
② 자식이 2개라면, 부모보다 작은 값의 왼쪽 자식 하나와 큰 값의 오른쪽 자식 하나를 가진다.
트리의 용어 — 맨 위 노드는 루트(root), 한 노드가 가리키는 노드들은 자식(children), 그 노드는 자식들의 부모(parent). 트리는 레벨(level)을 가진다.
class TreeNode: def __init__(self, val, left=None, right=None): self.value = val self.leftChild = left self.rightChild = right
§ 2 · 좌우로 갈라지며검색
이진 트리 검색은 루트에서 시작한다. 노드 값을 확인하고, 찾는 값이 더 작으면 왼쪽 부분 트리로, 더 크면 오른쪽 부분 트리로 내려간다. 매 단계 후보의 절반을 버린다 — O(log N)이다.
def search(value, node): if node is None or node.value == value: return node elif value < node.value: return search(value, node.leftChild) else: return search(value, node.rightChild)
§ 3 · 빈자리에 매달기삽입
이진 트리가 정렬된 배열보다 정말 빛나는 곳은 삽입이다. 새 값을 넣으려면 검색하듯 내려가다 자식이 없는 곳에 도달하면 거기 매단다. 검색(log N) + 삽입 1단계 = O(log N). 정렬된 배열의 O(N) 삽입과 대조된다.
§ 4 · 후속자 노드삭제
삭제는 이진 트리에서 가장 직관적이지 않은 연산이다.
- 자식이 없으면 — 그냥 삭제한다.
- 자식이 1개면 — 삭제하고 그 자리에 자식을 올린다.
- 자식이 2개면 — 노드를 후속자 노드(successor node)로 대체한다. 후속자는 삭제된 값보다 큰 값들 중 가장 작은 값이다.
후속자를 찾는 법 — 삭제된 노드의 오른쪽 자식으로 간 뒤, 왼쪽 자식이 없을 때까지 왼쪽으로 계속 내려간다. 검색·삽입처럼 삭제도 일반적으로 O(log N)이다.
§ 5 · 순서대로 방문중위 순회
책 제목을 알파벳 순서로 출력하려면 트리의 모든 노드를 순서대로 방문해야 한다. 자료구조의 모든 노드를 방문하는 것을 순회(traverse)라 하고, 오름차순으로 도는 방식이 중위 순회(inorder traversal)다.
def traverse_and_print(node): if node is None: return traverse_and_print(node.leftChild) # 왼쪽 먼저 print(node.value) # 자신 방문 traverse_and_print(node.rightChild) # 오른쪽 마지막
중위 순회는 모든 노드를 빠짐없이 방문하므로 O(N)이다. 왼쪽 → 자신 → 오른쪽 순서가 오름차순 출력을 보장한다.
§ 6 · 정리이 장이 남긴 것
이진 트리는 순서 유지와 빠른 검색·삽입·삭제를 동시에 제공하는 강력한 노드 기반 자료구조다. 데이터를 자주 수정하는 애플리케이션에서 진가를 발휘한다. 트리 기반 자료구조에는 힙, B-트리, 레드-블랙 트리 등도 있다. 다음 장에서는 또 다른 노드 기반 자료구조 — 그래프를 만난다.