📚 지식 노트

트리의 낱말

배열과 연결 리스트는 값을 한 줄로 늘어놓는다. 한 줄에서 원하는 값을 찾으려면 최악에는 끝까지 훑어야 하고(O(n)), 정렬해 두면 이진 탐색은 빨라지지만 중간에 넣고 빼는 데 또 O(n)이 든다. 트리(tree)는 값을 위아래 여러 갈래로 나눠 담아, 한 번 비교할 때마다 남은 후보의 상당 부분을 통째로 버리게 만든다. 갈래가 고르게 나뉘면 n개 가운데 하나를 찾는 데 비교가 log n번 정도면 된다. 한 줄 구조는 선형 자료구조 노트에 있다.

• 뿌리(root)·부모(parent)·자식(child): 모든 노드는 뿌리를 빼면 부모가 정확히 하나다. 같은 부모를 둔 노드끼리는 형제(sibling)다.
• 잎(leaf): 자식이 없는 노드. 자식이 있는 노드는 안쪽 노드(internal node)라 부른다.
• 깊이(depth): 뿌리에서 그 노드까지 간선 수. 높이(height): 뿌리에서 가장 먼 잎까지 간선 수. 이 노트의 연산은 대부분 높이에 비례하는 시간이 든다.
• 부분 트리(subtree): 한 노드와 그 아래 자손 전체. 트리 알고리즘은 "왼쪽 부분 트리에 맡긴다"처럼 재귀로 쓰기 좋다.
• 이진 트리(binary tree): 자식이 많아야 둘(왼쪽·오른쪽)인 트리. 노드 n개짜리 이진 트리의 높이는 가장 낮아도 ⌊log₂ n⌋, 가장 높으면 n − 1(한 줄)이다.

결국 트리 자료구조의 설계는 "높이를 어떻게 낮게 유지하는가"와 "노드에 무엇을 미리 적어 두는가" 두 질문으로 요약된다. 아래 절들은 그 답이 쓰임에 따라 어떻게 달라지는지를 보여 준다.

트리를 빠짐없이 한 번씩 도는 기본 순서는 넷이다. 전위(pre-order: 자신 → 왼쪽 → 오른쪽)는 부모를 자식보다 먼저 보므로 트리를 복사하거나 수식 트리를 접두 표기로 적을 때, 후위(post-order: 왼쪽 → 오른쪽 → 자신)는 자식을 먼저 끝내므로 트리를 지우거나 후위 표기로 적을 때 쓴다. 중위(in-order: 왼쪽 → 자신 → 오른쪽)는 다음 절의 이진 탐색 트리에서 값을 정렬 순서로 꺼낸다. 이 셋은 재귀(곧 스택)로 도는 깊이 우선이고, 레벨 순회(level-order)는 큐로 뿌리부터 한 층씩 넓혀 가는 너비 우선이다(그래프 노트의 BFS).

문제 풀기 →Python 코드 →

이진 탐색 트리

이진 탐색 트리(binary search tree, BST)는 모든 노드에서 "왼쪽 부분 트리의 값은 모두 작고, 오른쪽은 모두 크다"는 규칙을 지킨다. 찾을 값을 뿌리와 비교해 작으면 왼쪽, 크면 오른쪽으로 내려가면 되므로 정렬된 배열의 이진 탐색을 그대로 트리 모양으로 옮긴 셈이다. 배열과 다른 점은 넣고 빼도 다른 값을 밀어낼 필요가 없다는 것이다.

1. 찾기: 뿌리에서 비교하며 내려간다. 같은 값을 만나면 찾은 것이고, 빈 자리(null)에 닿으면 없는 것이다.
2. 넣기: 찾기와 똑같이 내려가다 빈 자리에 새 잎을 단다. 기존 노드는 하나도 움직이지 않는다.
3. 지우기: 잎이면 그냥 떼고, 자식이 하나면 그 자식이 자리를 잇는다. 자식이 둘이면 바로 뗄 수 없으니, 오른쪽 부분 트리의 가장 작은 값(후계자, in-order successor)을 그 자리에 복사하고 후계자를 대신 지운다. 후계자는 왼쪽 자식이 없으므로 앞의 쉬운 두 경우로 돌아간다.

세 연산 모두 O(h)다(h는 높이). 그리고 중위 순회(in-order traversal: 왼쪽 → 자신 → 오른쪽)를 하면 값이 작은 순서로 나온다. 그래서 BST는 단순한 집합이 아니라 "정렬된 사전"이 된다. 해시 테이블은 찾기가 평균 O(1)로 더 빠르지만 "k보다 큰 가장 작은 값", "a 이상 b 이하인 값 모두" 같은 순서 질의는 못 한다(해싱 노트).

약점은 높이가 입력 순서에 달려 있다는 것이다. 1, 2, 3, …을 차례로 넣으면 모든 노드가 오른쪽 자식으로만 이어져 연결 리스트가 되고 h = n − 1, 모든 연산이 O(n)으로 떨어진다. 실제 데이터는 정렬된 채 들어오는 일이 흔하므로, 실무의 BST는 거의 다 다음 절의 균형 장치를 단다.

문제 풀기 →Python 코드 →

회전과 균형: AVL 트리와 레드-블랙 트리

균형 이진 탐색 트리(self-balancing BST)는 넣기·지우기 뒤에 모양을 살짝 고쳐 높이를 O(log n)으로 묶는다. 도구는 회전(rotation)이다. 부모 y와 왼쪽 자식 x가 있을 때 오른쪽 회전은 x를 위로, y를 x의 오른쪽 자식으로 내리고, x의 원래 오른쪽 부분 트리를 y의 왼쪽에 옮겨 단다. 포인터 세 개만 바꾸는 O(1) 작업이고, 중위 순서(크기 순서)는 바뀌지 않는다. 왼쪽 회전은 그 거울상이다.

AVL 트리(1962년 Adelson-Velsky와 Landis)는 모든 노드에서 왼쪽·오른쪽 부분 트리의 높이 차(균형 인수)를 −1, 0, +1 안에 둔다. 넣은 뒤 길을 거슬러 올라가다 차이가 2가 된 노드를 만나면, 넣은 값이 어느 쪽 손자로 들어갔느냐에 따라 네 경우로 나눠 고친다.

넣기에서는 이렇게 한 곳만 고치면 그 위 조상들의 높이도 넣기 전으로 돌아가 끝난다. 지우기는 회전 뒤에 높이가 줄어 위로 불균형이 번질 수 있어 최악에 O(log n)번 회전한다. AVL의 높이는 약 1.44·log₂ n 이하로, 균형 트리 가운데 가장 낮은 편이라 찾기가 많은 쓰임에 유리하다.

레드-블랙 트리(red-black tree)는 높이 차를 직접 재는 대신 노드에 빨강·검정 색을 칠하고 규칙을 지킨다. 규칙이 느슨한 만큼 높이는 최대 2·log₂(n+1)로 AVL보다 조금 높을 수 있지만, 넣기·지우기 한 번에 회전이 많아야 두세 번이고 나머지는 색만 바꾸면 된다. 쓰기가 잦은 범용 정렬 사전에 많이 쓰인다.

둘 다 찾기·넣기·지우기가 최악에도 O(log n)이다. 최악을 보장한다는 점이 평균만 빠른 해시 테이블과의 차이이고, 실시간 처리처럼 "가끔 아주 느린" 것이 곤란한 곳에서 균형 트리를 고르는 이유가 된다. 더 자세한 그림은 Algorithms, 4th Edition의 균형 탐색 트리 장에 있다.

문제 풀기 →Python 코드 →

B-트리: 디스크를 위한 넓고 낮은 트리

이진 트리는 노드 하나를 볼 때마다 포인터 하나를 따라가야 한다. 메모리에서는 문제없지만, 데이터가 디스크나 SSD에 있으면 노드 하나 읽기가 곧 블록(수 KB) 한 번 읽기이고, 그 한 번이 메모리 접근보다 SSD는 수백 배, HDD는 10만 배쯤 느리다(저장 장치 노트). 노드 하나에 값 하나만 두면 블록을 거의 비운 채 읽는 셈이다.

B-트리(B-tree)는 노드 하나를 블록 하나 크기로 키워 열쇠를 수백 개씩 정렬해 담고, 열쇠 사이 틈마다 자식을 단다. 열쇠가 k개인 노드는 자식이 k+1개다. 한 노드 안에서는 이진 탐색으로 갈 자식을 고른다. 갈래가 수백 개이니 열쇠 10억 개도 높이 3~4면 담기고, 찾기 한 번에 디스크 읽기가 서너 번이면 끝난다. 뿌리와 윗층은 늘 캐시에 있어 실제로는 더 적다.

높이를 지키는 방식이 이진 균형 트리와 다르다. 새 열쇠는 늘 잎에 넣고, 잎이 넘치면 가운데 열쇠를 부모로 올리며 둘로 가른다. 부모가 넘치면 같은 일이 위로 번지고, 뿌리가 갈라질 때만 새 뿌리가 생겨 트리 전체가 한 층 높아진다. 트리가 아래가 아니라 위로 자라므로 모든 잎이 늘 같은 깊이에 있다. 지우기는 반대로 노드가 너무 비면 형제에게서 열쇠를 빌리거나 형제와 합친다. 차수가 m인 B-트리에서 뿌리가 아닌 안쪽 노드는 자식이 ⌈m/2⌉ 이상 m 이하라, 노드마다 공간이 절반 이상 찬다.

• B+ 트리: 실제 값(또는 행 위치)은 잎에만 두고 안쪽 노드에는 길잡이 열쇠만 둔다. 안쪽 노드에 열쇠가 더 들어가 트리가 낮아지고, 잎끼리 옆으로 이어 두면 범위 검색(BETWEEN, ORDER BY)을 잎만 따라 읽어 끝낸다. 데이터베이스 색인이 대개 이 모양이다.
• 쓰이는 곳: MySQL InnoDB와 PostgreSQL의 기본 색인, SQLite의 테이블과 색인, 파일 시스템의 디렉터리·메타데이터(NTFS, HFS+, XFS, Btrfs).
• 대안: 쓰기가 아주 많으면 LSM 트리(log-structured merge tree)처럼 쓰기를 모아 한꺼번에 정렬해 내리는 구조를 쓰기도 한다. B-트리는 읽기가 고르게 빠르고, LSM은 쓰기가 빠른 대신 읽기 때 여러 층을 뒤진다.

문제 풀기 →Python 코드 →

이진 힙과 우선순위 큐

"지금 가장 급한 것 하나"만 계속 꺼내면 되는 일이 많다. 운영체제 스케줄러, 다익스트라의 다음 점 고르기, 시뮬레이션의 다음 사건, 상위 k개 뽑기가 그렇다. 이런 우선순위 큐(priority queue)에 정렬 전체는 지나치다. 맨 앞 하나만 알면 되기 때문이다.

이진 힙(binary heap)은 규칙을 BST보다 훨씬 약하게 둔다. 최소 힙이면 "부모는 자식보다 작거나 같다"만 지키고, 형제끼리나 다른 갈래끼리는 순서가 없다. 대신 모양을 늘 완전 이진 트리(맨 아래 층만 왼쪽부터 채우다 만 꼴)로 유지해, 포인터 없이 배열 한 줄에 층 순서대로 담는다. i번 칸의 자식은 2i+1·2i+2번, 부모는 ⌊(i−1)/2⌋번이다.

배열에 빈틈 없이 붙어 있어 캐시에 잘 맞고 구현이 짧다는 것이 큰 장점이다. 파이썬 heapq, Java PriorityQueue, C++ std::priority_queue가 대개 이진 힙으로 구현된다. 힙에서 하나씩 꺼내 정렬하는 힙 정렬은 정렬 노트에, 힙을 쓰는 다익스트라는 그래프 노트에 있다. "이미 들어간 항목의 우선순위 낮추기"가 잦으면 위치표를 따로 두거나(색인 힙), 낡은 항목을 그냥 두고 꺼낼 때 버리는 방법을 쓴다.

"n개 가운데 가장 큰 k개"도 힙의 단골 문제다. 전부 정렬하면 O(n log n)이지만, 크기 k인 최소 힙을 두고 새 값이 힙의 최솟값보다 클 때만 바꿔 넣으면 한 번에 O(log k)라 전체 O(n log k)다(Wikipedia의 Partial sorting). 힙에는 늘 "지금까지 본 상위 k개"만 남고 값을 한 번씩만 보므로, 끝없이 들어오는 스트림에도 쓸 수 있다. 순서 없이 k번째 값 하나만 필요하면 평균 O(n)인 퀵 셀렉트(정렬 노트의 퀵 정렬 절)도 있다.

문제 풀기 →Python 코드 →

트라이: 글자로 갈라지는 트리

검색창 자동 완성은 "지금까지 친 글자로 시작하는 낱말"을 빨리 찾아야 한다. BST는 낱말 전체를 비교하며 내려가니 한 번 비교에 글자 수만큼 시간이 들고, 해시 테이블은 접두사 질의를 못 한다. 트라이(trie, prefix tree)는 노드가 값을 들지 않고 간선이 글자 하나를 뜻한다. 뿌리에서 c → a → r로 내려간 자리에 "여기서 낱말이 끝난다"는 표시를 달면 "car"가 저장된다.

• 시간: 길이 L인 낱말의 찾기·넣기는 O(L)이다. 저장된 낱말이 몇 개든 상관없다. 접두사 p로 시작하는 낱말을 모두 모으는 데는 O(|p| + 결과 크기)가 든다.
• 공간: 노드마다 자식 표를 둬야 해 메모리를 많이 쓴다. 알파벳 26칸 배열이면 빠르지만 대부분 비고, 해시나 정렬 목록이면 작지만 느리다.
• 압축 트라이(radix tree, Patricia tree): 갈래가 없는 외길을 한 간선으로 합쳐 노드 수를 줄인다. 그림의 c → a처럼 갈래도 낱말 끝도 없는 외길이 "ca" 한 간선으로 합쳐진다.
• 쓰이는 곳: 자동 완성과 맞춤법 검사, 라우터가 목적지 IP와 가장 길게 겹치는 경로를 고르는 최장 접두사 일치(longest prefix match, 네트워크 노트), 여러 패턴을 한 번에 찾는 아호-코라식(문자열 노트).

문제 풀기 →Python 코드 →

세그먼트 트리와 펜윅 트리: 구간 질의

배열에서 "i번부터 j번까지의 합(또는 최솟값)"을 자주 묻는데 값도 자주 바뀐다고 하자. 매번 더하면 질의가 O(n)이다. 앞에서부터의 누적 합 배열을 만들어 두면 질의는 O(1)이지만, 값 하나가 바뀌면 그 뒤 누적 합을 모두 고쳐야 해 갱신이 O(n)이다. 둘 다 O(log n)으로 맞추는 것이 이 절의 두 트리다.

세그먼트 트리(segment tree)는 배열을 반씩 나눈 구간마다 노드를 하나 두고, 그 구간의 합을 적어 둔다. 뿌리는 전체, 그 두 자식은 앞 절반과 뒤 절반, …, 잎은 칸 하나다. 질의 구간을 만나면 통째로 들어가는 노드는 저장된 합을 그대로 쓰고, 걸치는 노드만 두 자식으로 내려간다. 값 하나를 바꾸면 그 잎에서 뿌리까지 log n개 노드의 합만 고치면 된다.

합 대신 최솟값·최댓값·최대공약수처럼 두 구간의 답을 합쳐 큰 구간의 답을 낼 수 있는(결합 법칙이 성립하는) 연산이면 무엇이든 담을 수 있다. 구간 전체에 같은 값을 더하는 갱신은 "나중에 자식에게 내려 줄 몫"을 노드에 적어 두는 지연 전파(lazy propagation)로 O(log n)에 처리한다. 자세한 구현은 cp-algorithms의 세그먼트 트리 글이 잘 정리했다.

펜윅 트리(Fenwick tree, binary indexed tree)는 같은 일을 배열 하나로 더 가볍게 한다. 1부터 센 i번 칸에 "i에서 끝나고 길이가 i의 가장 낮은 1비트(lowbit)인 구간"의 합을 적는다. 앞 i칸 합은 i에서 lowbit를 빼 가며 칸을 더하면 되고, 값을 바꿀 때는 i에 lowbit를 더해 가며 칸을 고친다. 둘 다 비트가 하나씩 사라지거나 올라가므로 O(log n)이다.

실무에서는 시계열 데이터베이스의 구간 집계, 게임의 순위표(내 점수보다 높은 사람 수 세기), 계산 기하의 스위핑 같은 곳에 쓰인다. 구간을 다루는 다른 기법(두 포인터, 분할 정복)은 알고리즘 기법 노트에 있다.

문제 풀기 →Python 코드 →