알고리즘

트리와 힙

트리 용어와 순회, 이진 탐색 트리의 탐색·삽입·삭제, 이진 힙과 우선순위 큐를 동작 원리와 복잡도, 구현 코드로 익힙니다.

트리는 루트에서 시작해 부모와 자식으로 이어지는 계층형 자료구조입니다. 모든 노드의 자식이 두 개 이하인 이진 트리에 "왼쪽은 작고 오른쪽은 크다"는 규칙을 더하면 이진 탐색 트리(BST)가 되고, "부모가 자식보다 작거나 같다"는 규칙과 완전 이진 트리 모양을 더하면 이진 힙이 됩니다. 이 주제에서는 트리 용어, 네 가지 순회, BST, 균형 트리, 힙과 우선순위 큐를 함께 다룹니다.

트리와 힙은 실무 시스템의 뼈대입니다. 데이터베이스 인덱스는 B-트리, C++ std::map과 Java TreeMap은 레드-블랙 트리, 운영체제 스케줄러와 타이머, 다익스트라 최단 경로는 트리나 힙에 기대어 동작합니다. 높이가 성능을 좌우한다는 점, 힙이 배열 하나에 담긴다는 점을 이해하면 언제 어떤 구조를 고를지 판단할 수 있고, 코딩 테스트와 기술 면접에서도 자주 묻는 내용입니다.

먼저 작은 트리를 종이에 그려 전위·중위·후위·레벨 순회를 손으로 따라가 보세요. 이어서 BST의 삽입·탐색·삭제와 힙의 sift up·sift down을 직접 구현하고, heapify가 O(n)인 이유를 확인합니다. 마지막으로 Python heapq, C++ priority_queue, Java PriorityQueue 같은 표준 도구로 상위 K개, 정렬된 목록 병합 같은 문제를 풀어 보면 개념이 단단해집니다.

특징

트리 용어와 순회

루트·잎·깊이·높이 같은 용어와 전위·중위·후위·레벨 순회를 익히면 대부분의 트리 문제를 읽고 풀 수 있습니다.

이진 탐색 트리

왼쪽은 작고 오른쪽은 큰 규칙 덕분에 탐색·삽입·삭제가 트리 높이에 비례하고, 중위 순회로 정렬 순서를 얻습니다.

균형 유지

정렬된 입력에서 BST는 연결 리스트처럼 길어집니다. AVL 트리와 레드-블랙 트리는 회전으로 높이를 O(log n)으로 지킵니다.

이진 힙과 우선순위 큐

완전 이진 트리를 배열에 담아 최솟값 확인은 O(1), 삽입과 꺼내기는 O(log n), 배열 전체 heapify는 O(n)에 처리합니다.

이런 곳에 씁니다

대표 구현

BST와 최소 힙 구현

Node 클래스로 이진 탐색 트리를 만들고, bst_insert는 키를 비교하며 빈자리를 찾아 새 노드를 붙이고 bst_search는 반복문으로 내려가며 키를 찾습니다. 중위 순회 결과가 오름차순인지 확인할 수 있습니다. MinHeap은 리스트에 원소를 담고 push에서는 sift up, pop에서는 sift down으로 힙 성질을 지키므로 꺼낸 값이 작은 순서로 나옵니다.

trees_and_heaps.py

# Binary search tree (insert/search) and a binary min-heap
class Node:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None


def bst_insert(root, key):
    if root is None:
        return Node(key)
    if key < root.key:
        root.left = bst_insert(root.left, key)
    elif key > root.key:
        root.right = bst_insert(root.right, key)
    return root  # duplicates are ignored


def bst_search(root, key):
    while root is not None and root.key != key:
        root = root.left if key < root.key else root.right
    return root is not None


def inorder(root, out):
    if root is not None:
        inorder(root.left, out)
        out.append(root.key)
        inorder(root.right, out)
    return out


class MinHeap:
    def __init__(self):
        self.a = []

    def push(self, x):
        a = self.a
        a.append(x)
        i = len(a) - 1
        while i > 0 and a[(i - 1) // 2] > a[i]:  # sift up
            p = (i - 1) // 2
            a[i], a[p] = a[p], a[i]
            i = p

    def pop(self):
        a = self.a
        top, last = a[0], a.pop()
        if a:
            a[0] = last
            i, n = 0, len(a)
            while True:  # sift down
                small = i
                for c in (2 * i + 1, 2 * i + 2):
                    if c < n and a[c] < a[small]:
                        small = c
                if small == i:
                    break
                a[i], a[small] = a[small], a[i]
                i = small
        return top

    def __len__(self):
        return len(self.a)


root = None
for k in [50, 30, 70, 20, 40, 60, 80]:
    root = bst_insert(root, k)
print(inorder(root, []))                     # [20, 30, 40, 50, 60, 70, 80]
print(bst_search(root, 60), bst_search(root, 65))  # True False

heap = MinHeap()
for x in [5, 3, 8, 1, 9, 2]:
    heap.push(x)
print([heap.pop() for _ in range(len(heap))])  # [1, 2, 3, 5, 8, 9]

python trees_and_heaps.py