복잡도

트리 연산의 비용은 대부분 높이 h로 결정됩니다. 노드 수 n과 높이의 관계만 이해하면 BST와 힙의 복잡도가 자연스럽게 나옵니다. 이 장에서는 연산별 시간 · 공간 복잡도를 정리하고, heapify가 O(n)인 이유와 다른 자료구조와의 비교를 다룹니다.

높이와 노드 수

높이가 h인 이진 트리의 노드 수는 많아야 2^(h+1) - 1개입니다. 거꾸로 말하면 노드가 n개인 이진 트리의 높이는 적어도 약 log2 n이고, 많아야 n - 1(편향 트리)입니다. 완전 이진 트리인 힙은 항상 최소 높이 floor(log2 n)를 가지므로 최악의 경우에도 O(log n)이 보장됩니다. 반면 일반 BST는 입력 순서에 따라 높이가 달라집니다.

import random


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)
    cur = root
    while True:
        side = "left" if key < cur.key else "right"
        if getattr(cur, side) is None:
            setattr(cur, side, Node(key))
            return root
        cur = getattr(cur, side)


def height(root):
    best, stack = -1, [(root, 0)] if root else []
    while stack:
        node, d = stack.pop()
        best = max(best, d)
        stack += [(c, d + 1) for c in (node.left, node.right) if c]
    return best


n = 2000
keys = list(range(n))
for name, order in [("정렬된 입력", keys), ("무작위 입력", random.sample(keys, n))]:
    root = None
    for k in order:
        root = insert(root, k)
    print(name, height(root))
# 정렬된 입력 1999
# 무작위 입력 약 20~30 (실행마다 다름)

무작위 순서로 넣은 BST의 평균 높이는 O(log n)이지만, 실제 입력은 정렬되어 있거나 거의 정렬된 경우가 많습니다. 그래서 최악을 보장해야 하는 곳에서는 AVL 트리나 레드-블랙 트리 같은 균형 트리를 씁니다.

연산별 복잡도

힙은 임의의 값을 찾는 데는 약하고(전체를 봐야 함), 최솟값만 다룰 때 강합니다. BST는 모든 연산이 고르게 O(log n)이지만 상수 비용과 메모리가 더 큽니다.

순회의 비용

모든 순회는 노드를 한 번씩 방문하므로 시간은 O(n)입니다. 추가 공간은 재귀 스택이나 명시적 스택의 크기로, 깊이 우선 순회는 O(h), 레벨 순회는 가장 넓은 레벨의 노드 수(완전 이진 트리에서 약 n/2)만큼 필요합니다. 편향 트리에서는 h가 n에 가까워 Python의 재귀 한도를 넘을 수 있으므로 스택을 직접 쓰는 반복 버전을 알아 두면 좋습니다.

def inorder_iter(root):
    out, stack, cur = [], [], root
    while stack or cur:
        while cur:                 # 왼쪽 끝까지 내려가며 쌓기
            stack.append(cur)
            cur = cur.left
        cur = stack.pop()
        out.append(cur.key)
        cur = cur.right
    return out


root = None
for k in range(5000):              # 높이 4999 인 편향 트리
    root = insert(root, k)
print(len(inorder_iter(root)))     # 5000, 재귀 한도 문제 없음

heapify가 O(n)인 이유

heapify는 높이가 k인 노드를 최대 k번 내립니다. 완전 이진 트리에서 높이가 k인 노드는 약 n / 2^(k+1)개이므로 전체 비용은 n x (1/4 + 2/8 + 3/16 + ...) 꼴이 되고, 이 급수는 상수(1)로 수렴합니다. 즉 대부분의 노드는 잎 근처에 있어 거의 움직이지 않습니다. 반대로 원소를 하나씩 push하면 아래쪽 노드들이 위로 길게 올라갈 수 있어 O(n log n)입니다.

import heapq


class Counted:
    count = 0

    def __init__(self, v):
        self.v = v

    def __lt__(self, other):
        Counted.count += 1
        return self.v < other.v


data = list(range(100_000, 0, -1))   # 내림차순: push 의 최악 입력

Counted.count = 0
heapq.heapify([Counted(v) for v in data])
print("heapify", Counted.count)      # 약 150,000 (약 1.5n)

Counted.count = 0
h = []
for v in data:
    heapq.heappush(h, Counted(v))
print("push n번", Counted.count)     # 약 1,470,000 (n log n 수준)

다른 자료구조와 비교

공간은 모두 O(n)이지만, 힙은 배열 하나에 담겨 포인터가 필요 없고 메모리 지역성이 좋아 실제로 빠릅니다. BST는 노드마다 자식 포인터 두 개(균형 트리는 높이나 색 정보까지)를 더 가집니다.

정리

트리 연산의 비용은 높이가 결정합니다. 힙은 모양이 완전 이진 트리로 고정되어 삽입 · 꺼내기가 항상 O(log n)이고 heapify는 O(n)입니다. BST는 평균 O(log n)이지만 정렬된 입력에서 O(n)으로 무너지므로, 최악을 보장하려면 균형 BST를 씁니다. 깊은 트리에서는 재귀 대신 명시적 스택을 고려합니다.