동작 원리

이 장에서는 작은 예제를 손으로 따라가며 트리 순회, 이진 탐색 트리의 삽입 · 탐색 · 삭제, 힙의 sift up · sift down과 heapify가 어떻게 움직이는지 살펴봅니다. 예제 트리는 키 50, 30, 70, 20, 40, 60, 80을 이 순서대로 BST에 넣어 만든 것입니다.

          50
        /    \
      30      70
     /  \    /  \
   20   40  60   80

네 가지 순회

순회는 모든 노드를 한 번씩 방문하는 방법입니다. 깊이 우선 순회 세 가지는 "자신을 언제 방문하느냐"만 다릅니다.

전위 순회는 트리를 복사하거나 직렬화할 때, 중위 순회는 BST를 정렬 순서로 읽을 때, 후위 순회는 자식 결과를 모아 부모를 계산할 때(폴더 크기 합, 트리 삭제) 씁니다. 레벨 순회는 큐를 쓰는 너비 우선 탐색(BFS)입니다.

from collections import deque


class Node:
    def __init__(self, key):
        self.key, self.left, self.right = key, None, None


def insert(root, key):
    if root is None:
        return Node(key)
    if key < root.key:
        root.left = insert(root.left, key)
    elif key > root.key:
        root.right = insert(root.right, key)
    return root


def preorder(n):
    return [n.key] + preorder(n.left) + preorder(n.right) if n else []


def inorder(n):
    return inorder(n.left) + [n.key] + inorder(n.right) if n else []


def postorder(n):
    return postorder(n.left) + postorder(n.right) + [n.key] if n else []


def level_order(root):
    out, queue = [], deque([root] if root else [])
    while queue:
        n = queue.popleft()
        out.append(n.key)
        if n.left:
            queue.append(n.left)
        if n.right:
            queue.append(n.right)
    return out


root = None
for k in [50, 30, 70, 20, 40, 60, 80]:
    root = insert(root, k)
print(preorder(root), inorder(root), postorder(root), level_order(root), sep="\n")

BST 탐색과 삽입

60을 찾는 과정은 다음과 같습니다. 50과 비교해 크므로 오른쪽(70)으로, 70보다 작으므로 왼쪽(60)으로 가서 찾습니다. 비교 세 번이면 됩니다. 65를 찾으면 60의 오른쪽 자식이 비어 있는 곳에서 멈추고 "없음"을 돌려줍니다. 삽입은 바로 그 빈자리에 새 노드를 붙이는 것입니다. 즉 65를 넣으면 60의 오른쪽 자식이 됩니다.

BST 삭제의 세 가지 경우

삭제는 지울 노드의 자식 수에 따라 나뉩니다.

• 자식이 없으면(20): 그냥 떼어 냅니다.
• 자식이 하나면: 그 자식을 지울 노드 자리로 끌어올립니다.
• 자식이 둘이면(30): 오른쪽 서브트리의 최솟값, 즉 중위 후속자(40)를 찾아 키를 복사한 뒤, 오른쪽 서브트리에서 그 후속자를 지웁니다. 후속자는 왼쪽 자식이 없으므로 앞의 두 경우로 끝납니다.

def delete(root, key):
    if root is None:
        return None
    if key < root.key:
        root.left = delete(root.left, key)
    elif key > root.key:
        root.right = delete(root.right, key)
    else:
        if root.left is None:
            return root.right
        if root.right is None:
            return root.left
        succ = root.right
        while succ.left:
            succ = succ.left
        root.key = succ.key
        root.right = delete(root.right, succ.key)
    return root


root = delete(root, 30)
print(inorder(root), preorder(root))
# [20, 40, 50, 60, 70, 80] [50, 40, 20, 70, 60, 80]

힙 삽입: sift up

최소 힙 [1, 3, 2, 7, 4, 5]에 0을 넣어 봅니다. 완전 이진 트리 모양을 지키려고 먼저 배열 끝(인덱스 6)에 붙인 뒤, 부모보다 작은 동안 부모와 자리를 바꿉니다.

최솟값 꺼내기: sift down

루트(0)를 꺼낸 다음, 마지막 원소(2)를 루트로 옮기고 더 작은 자식과 바꾸며 내려갑니다.

heapify: 배열을 한 번에 힙으로

원소 n개를 하나씩 넣으면 O(n log n)이 들지만, 마지막 내부 노드(인덱스 n // 2 - 1)부터 루트까지 거꾸로 sift down을 하면 O(n)에 힙이 됩니다. 대부분의 노드는 잎 근처에 있어 조금만 내려가면 되기 때문입니다.

def sift_down(a, i, n):
    while True:
        small, l, r = i, 2 * i + 1, 2 * i + 2
        if l < n and a[l] < a[small]:
            small = l
        if r < n and a[r] < a[small]:
            small = r
        if small == i:
            return
        a[i], a[small] = a[small], a[i]
        i = small


def heapify(a):
    for i in range(len(a) // 2 - 1, -1, -1):
        sift_down(a, i, len(a))
        print(f"i={i}: {a}")


heapify([9, 5, 7, 1, 3, 2])
# i=2: [9, 5, 2, 1, 3, 7]
# i=1: [9, 1, 2, 5, 3, 7]
# i=0: [1, 3, 2, 5, 9, 7]

정리

깊이 우선 순회 세 가지는 자신을 방문하는 시점만 다르고, 레벨 순회는 큐로 구현합니다. BST는 비교 한 번마다 한쪽으로 내려가 탐색 · 삽입하며, 자식이 둘인 노드는 중위 후속자로 바꿔 지웁니다. 힙은 끝에 붙이고 위로 올리는 sift up, 루트를 바꾸고 아래로 내리는 sift down 두 동작만으로 우선순위 큐를 유지하며, heapify는 아래쪽부터 sift down을 해 O(n)에 힙을 만듭니다.