학습 목표
이번 주차를 마치면 다음을 할 수 있습니다:
- 트리 용어(루트, 잎, 부모, 자식, 높이, 깊이)를 쓰고, 노드 구조체가 메모리에 어떻게 놓이는지 그릴 수 있다
- 이진 트리를 손으로 조립하고 네 가지 순회(전위, 중위, 후위, 레벨)를 코드 없이 종이에서 수행할 수 있다
- 재귀 순회를 스택 기반 반복문으로 바꿀 수 있고, 왜 그래야 하는 경우가 있는지 안다
- 이진 탐색 트리(BST)의 탐색, 삽입, 삭제를 구현하고, 삭제의 세 경우를 설명할 수 있다
- BST를 올바르게 검증하는 방법과 순진한 검증의 함정을 안다
- AVL 트리의 균형 인수와 회전 4종을 이해하고, 정렬된 입력이 왜 위험한지 숫자로 안다
- 배열 기반 힙으로 O(log n) 우선순위 큐와 힙 정렬을 만들 수 있다
- 트리를 반드시 후위 순회로 해제해야 하는 이유를 도구(컴파일러 경고, Valgrind, AddressSanitizer)로 확인할 수 있다
들어가며
1주차에 터미널을 배우면서 리눅스의 폴더 구조를 이렇게 그렸습니다.
/
├── home
│ └── user
│ ├── 문서
│ └── 다운로드
└── usr
├── bin
└── include
이 그림은 무엇일까요? 10주차와 11주차에 만든 자료구조는 전부 한 줄이었습니다. 배열도, 연결 리스트도, 스택도, 큐도 데이터가 일렬로 서 있었죠. 그런데 폴더 구조는 한 줄이 아닙니다. / 아래에 home 과 usr 이 있고, 그 아래에 또 여럿이 있습니다. 데이터가 가지를 칩니다. 이것이 트리(tree) 입니다.
트리는 여러분 주변에 이미 가득합니다.
- 컴퓨터의 폴더 구조가 트리입니다.
du명령이 폴더 크기를 구하는 방법이 이번 주 프로젝트 1입니다. - 웹 페이지의 HTML 이 트리(DOM)입니다.
- 1주차 7절에서 본 컴파일러는 여러분의 C 코드를 먼저 트리(AST) 로 바꿉니다. 이번 주 프로젝트 2에서 그 축소판을 직접 만듭니다.
- 데이터베이스의 인덱스도 트리(B-트리)입니다. 13주차에서 만납니다.
- 회사 조직도, 토너먼트 대진표, 가계도. 계층이 있는 곳에는 어디나 트리가 있습니다.
그런데 트리가 자료구조로서 특별한 이유는 따로 있습니다. 찾는 것이 빠르기 때문입니다. 10주차에 연결 리스트에서 값 하나를 찾으려면 처음부터 끝까지 훑어야 했습니다(100만 개면 최악 100만 번). 이번 주에 만들 이진 탐색 트리는 같은 100만 개에서 약 20번 만에 찾습니다. 어떻게 그게 가능한지, 그리고 그 약속이 언제 깨지는지가 이번 주의 핵심입니다.
이번 주는 Part 2 에서 가장 내용이 많은 주입니다. 예제 10개와 프로젝트 3개가 있고, 5주차에서 배운 재귀가 거의 모든 코드에 등장합니다. 재귀가 아직 낯설다면 5주차 5절을 먼저 다시 읽고 오세요. 그리고 이번 주는 종이와 연필을 옆에 두세요. 트리는 머릿속으로만 그리면 반드시 헷갈립니다. 노드를 그리고 화살표가 움직이는 것을 따라가는 것이 가장 빠른 길입니다.
예제는 모두 week12 폴더에서 make 로 한 번에 빌드합니다. 5주차에 배운 그 make 입니다.
$ cd ~/c_programming/week12 # 저장소를 받은 위치에 맞게
$ make
컴파일: examples/avl_tree.c
컴파일: examples/binary_tree_basic.c
컴파일: examples/bst_delete.c
컴파일: examples/bst_insert_search.c
컴파일: examples/bst_validate.c
컴파일: examples/heap_basic.c
컴파일: examples/heap_pq_compare.c
컴파일: examples/heap_sort.c
컴파일: examples/level_order.c
컴파일: examples/traversal_iterative.c
✓ 예제 파일 빌드 완료
컴파일: projects/expr_parser.c
컴파일: projects/file_tree.c
컴파일: projects/task_manager.c
✓ 프로젝트 파일 빌드 완료
✓ 모든 파일 빌드 완료!
$ ls build | wc -l
13
실행 파일은 전부 build/ 안에 생깁니다. 이 글에서 ./build/이름 으로 실행하는 것이 그 파일들입니다.
1. 트리 용어와 노드 구조체
1.1 용어 먼저
트리를 이야기하려면 단어가 몇 개 필요합니다. 아래 그림 하나에 전부 들어 있습니다.
1 ← 루트(root): 맨 위. 부모가 없는 유일한 노드
/ \
2 3 ← 2와 3은 1의 자식(child), 1은 2와 3의 부모(parent)
/ \ \ 2와 3은 서로 형제(sibling)
4 5 6 ← 자식이 없는 노드 = 잎(leaf). 4, 5, 6
| 용어 | 뜻 | 위 그림에서 |
|---|---|---|
| 노드(node) | 데이터를 담은 동그라미 하나 | 1~6, 여섯 개 |
| 간선(edge) | 노드를 잇는 선 | 다섯 개 |
| 루트(root) | 부모가 없는 시작 노드 | 1 |
| 잎(leaf) | 자식이 없는 노드 | 4, 5, 6 |
| 깊이(depth) | 루트에서 그 노드까지 내려온 간선 수 | 1은 0, 2와 3은 1, 4·5·6은 2 |
| 높이(height) | 그 노드에서 가장 먼 잎까지의 간선 수 | 트리 전체(루트)의 높이는 2 |
| 부분트리(subtree) | 어떤 노드와 그 아래 전부 | “2의 부분트리”는 2, 4, 5 |
| 이진 트리(binary tree) | 자식이 최대 두 개인 트리 | 위 그림. 자식을 왼쪽·오른쪽으로 구분합니다 |
깊이는 위에서 세고 높이는 아래에서 셉니다. 헷갈리기 쉬운데, “루트의 깊이는 0, 잎의 높이는 0” 두 가지만 기억하면 됩니다. 노드 하나짜리 트리는 높이 0이고, 빈 트리의 높이는 −1 로 정합니다. 왜 −1인지는 곧 코드에서 자연스럽게 나옵니다.
그리고 이번 주 전체를 관통하는 한 문장이 있습니다.
트리 = 루트 + 왼쪽 부분트리 + 오른쪽 부분트리
이 정의를 보세요. “트리”를 설명하는 데 “부분트리”, 즉 트리가 또 나옵니다. 정의 자체가 재귀적입니다. 그래서 트리를 다루는 코드는 거의 전부 재귀로 짧고 자연스럽게 떨어집니다. 5주차에서 재귀를 배울 때 “재귀가 빛나는 곳”으로 하노이의 탑을 들었는데, 진짜 재귀의 고향은 트리입니다.
1.2 노드 구조체
10주차의 연결 리스트 노드를 떠올려 보세요. 데이터 하나에 next 포인터 하나였습니다. 이진 트리의 노드는 포인터가 하나 더 있을 뿐입니다.
typedef struct TNode {
int data;
struct TNode *left;
struct TNode *right;
} TNode;
struct TNode라는 이름을 안에서 다시 쓰는 것은 10주차의struct Node와 같은 이유입니다.typedef로TNode라는 별명이 완성되기 전이라, 구조체 안에서는 원래 이름으로 자기 자신을 가리켜야 합니다.left,right는 각각 왼쪽 자식과 오른쪽 자식의 주소입니다. 자식이 없으면NULL입니다.- 이 구조체 하나가 “트리”가 아닙니다. 노드 하나입니다. 트리는 노드들이 포인터로 이어진 모양 전체이고, 우리는 루트 노드의 주소 하나만 들고 다닙니다. 리스트에서
head하나만 들고 다녔던 것과 같습니다.
노드를 만드는 함수는 매번 똑같은 모양입니다.
TNode *node_create(int data) {
TNode *node = malloc(sizeof(TNode));
if (node == NULL) exit(1);
node->data = data;
node->left = node->right = NULL; /* 자식 없음으로 시작 */
return node;
}
node->left = node->right = NULL; 은 대입 두 개를 한 줄에 쓴 것입니다. 3주차에서 배운 대로 대입은 오른쪽부터 계산되므로 right 에 NULL 이 먼저 들어가고, 그 결과(NULL)가 다시 left 에 들어갑니다.
1.3 메모리에는 어떻게 놓일까
포인터로 이어진 구조는 항상 실제 주소로 한번 봐야 감이 옵니다. 6주차에서 한 것처럼 노드 여섯 개를 만들고 주소를 찍어 보겠습니다. 위 그림의 트리를 손으로 조립하는 코드입니다.
TNode *root = node_create(1);
root->left = node_create(2);
root->right = node_create(3);
root->left->left = node_create(4);
root->left->right = node_create(5);
root->right->right = node_create(6);
root->left->left 는 “루트의 왼쪽 자식의 왼쪽 자식”입니다. -> 를 왼쪽부터 차례로 따라가면 됩니다. 각 노드의 주소와 두 포인터가 가리키는 곳을 표로 찍으면 이렇습니다(addr.c, 주소는 실행마다 다릅니다).
sizeof(TNode) = 24
data 주소(노드) left right
1 0x5a1f795d42a0 0x5a1f795d42c0 0x5a1f795d42e0
2 0x5a1f795d42c0 0x5a1f795d4300 0x5a1f795d4320
3 0x5a1f795d42e0 (nil) 0x5a1f795d4340
4 0x5a1f795d4300 (nil) (nil)
5 0x5a1f795d4320 (nil) (nil)
6 0x5a1f795d4340 (nil) (nil)
이 표가 곧 트리입니다. 그림으로 옮기면 이렇습니다.
주소 ...42a0 [ 1 | left=...42c0 | right=...42e0 ]
│ │
┌────────────┘ └───────────┐
▼ ▼
...42c0 [ 2 | left=...4300 | right=...4320 ] ...42e0 [ 3 | left=NULL | right=...4340 ]
│ │ │
▼ ▼ ▼
...4300 [ 4 | NULL | NULL ] ...4320 [ 5 | NULL | NULL ] ...4340 [ 6 | NULL | NULL ]
세 가지를 눈여겨보세요.
sizeof(TNode)는 24바이트입니다.int4바이트와 포인터 8바이트 두 개를 더하면 20인데 24가 나왔습니다. 8주차에서 배운 패딩입니다. 포인터는 8의 배수 주소에 놓여야 해서int뒤에 4바이트가 비어 있습니다. 노드가 100만 개면 이 빈칸만 4MB입니다.- 노드들이 32바이트 간격으로 놓였습니다(
42a0,42c0,42e0…). 10주차에서 본 대로malloc은 24바이트를 달라고 해도 관리 정보를 포함해 32바이트 단위로 내줍니다. - 잎 노드의
left와right는 모두(nil), 즉NULL입니다. 앞으로 나오는 모든 재귀 함수는 이NULL을 만났을 때 멈춥니다.NULL이 재귀의 종료 조건입니다.
이 여섯 노드짜리 트리를 이번 주 첫 예제에서 그대로 씁니다.
2. 재귀 순회: 트리를 한 바퀴 도는 세 가지 순서
2.1 순회란
트리의 모든 노드를 한 번씩 방문하는 것을 순회(traversal) 라고 합니다. 리스트라면 처음부터 끝까지 한 방향으로 가면 끝이지만, 트리는 갈림길이 있습니다. 노드 하나에 서서 할 일이 세 가지입니다. 나를 처리하기, 왼쪽으로 내려가기, 오른쪽으로 내려가기. 이 셋을 어떤 순서로 하느냐에 따라 순회 이름이 붙습니다.
| 이름 | 순서 | 이름의 뜻 |
|---|---|---|
| 전위(pre-order) | 나 → 왼쪽 → 오른쪽 | 나를 먼저(pre) |
| 중위(in-order) | 왼쪽 → 나 → 오른쪽 | 나를 가운데(in) |
| 후위(post-order) | 왼쪽 → 오른쪽 → 나 | 나를 나중에(post) |
“왼쪽으로 내려가기”는 “왼쪽 부분트리를 같은 방식으로 순회하기”입니다. 부분트리도 트리이므로, 같은 함수를 다시 부르면 됩니다. 재귀입니다.
2.2 코드: printf 의 위치만 다르다
examples/binary_tree_basic.c 의 세 함수입니다.
/* 전위 순회 (Pre-order): 루트 -> 왼쪽 -> 오른쪽
* "나부터 처리하고 내려간다" - 트리 복사, 디렉토리 출력에 사용 */
void preorder(const TNode *root) {
if (root == NULL) return; /* 재귀의 종료 조건 */
printf("%d ", root->data);
preorder(root->left);
preorder(root->right);
}
/* 중위 순회 (In-order): 왼쪽 -> 루트 -> 오른쪽
* BST에서 이 순서로 돌면 "정렬된 순서"가 나온다! (다음 예제에서 확인) */
void inorder(const TNode *root) {
if (root == NULL) return;
inorder(root->left);
printf("%d ", root->data);
inorder(root->right);
}
/* 후위 순회 (Post-order): 왼쪽 -> 오른쪽 -> 루트
* "자식부터 처리하고 나를 처리한다" - 트리 해제, 폴더 크기 합산에 사용 */
void postorder(const TNode *root) {
if (root == NULL) return;
postorder(root->left);
postorder(root->right);
printf("%d ", root->data);
}
세 함수는 printf 한 줄의 위치만 다릅니다. 나머지는 완전히 같습니다.
const TNode *root: 순회는 트리를 읽기만 하므로const를 붙였습니다. 이 함수 안에서root->data = 0같은 수정을 시도하면 컴파일러가 막습니다.if (root == NULL) return;: 종료 조건. 빈 트리(또는 잎의 자식)에 도착하면 아무것도 하지 않고 돌아갑니다. 5주차에서 “종료 조건을 빼먹으면 스택 오버플로”라고 했던 그 조건입니다. 트리 함수는 거의 예외 없이 이 한 줄로 시작합니다.preorder(root->left);: 왼쪽 부분트리에 대해 나 자신을 다시 부릅니다. 이 호출이 끝나면(왼쪽을 다 돌면) 다음 줄로 넘어갑니다.
실행해 봅시다.
$ ./build/binary_tree_basic
=== 트리 모양 (왼쪽으로 90도 눕힘) ===
6
3
1
5
2
4
=== 세 가지 재귀 순회 ===
전위 (루트-좌-우): 1 2 4 5 3 6
중위 (좌-루트-우): 4 2 5 1 3 6
후위 (좌-우-루트): 4 5 2 6 3 1
=== 재귀로 구하는 트리 정보 ===
노드 개수: 6
높이 : 2 (루트에서 가장 먼 잎까지의 간선 수)
=== 해제는 왜 후위 순회인가 ===
전위로 지우면? 루트를 먼저 free -> 자식 주소를 잃는다 (UAF!)
후위로 지우면? 자식 먼저, 나는 마지막. 안전!
해제 완료 (valgrind로 누수 0 확인 가능)
맨 위의 “트리 모양”은 뒤에서 설명합니다. 먼저 순회 결과를 봅시다. 같은 트리인데 세 순서가 전부 다릅니다.
2.3 한 단계씩 따라가기
inorder(root) 가 어떻게 4 2 5 1 3 6 을 만드는지 손으로 따라가 봅시다. 5주차에서 재귀를 추적할 때 쓴 방법 그대로, 호출이 쌓이고 풀리는 순서를 적습니다. 들여쓰기가 깊을수록 재귀가 깊은 것입니다.
inorder(1)
inorder(2) ← 1의 왼쪽
inorder(4) ← 2의 왼쪽
inorder(NULL) → 즉시 return ← 4의 왼쪽은 없다
출력 4
inorder(NULL) → 즉시 return
출력 2 ← 4를 다 돌고 돌아와서 2 출력
inorder(5) ← 2의 오른쪽
inorder(NULL) → return
출력 5
inorder(NULL) → return
출력 1 ← 왼쪽 전체(4 2 5)를 끝내고 나서야 1
inorder(3) ← 1의 오른쪽
inorder(NULL) → return ← 3의 왼쪽은 없다
출력 3
inorder(6)
inorder(NULL) → return
출력 6
inorder(NULL) → return
출력만 모으면 4 2 5 1 3 6 입니다. 중요한 점은 1 이 네 번째로 출력된다는 것입니다. inorder(1) 은 맨 처음 불렸지만, 자기 왼쪽 부분트리(2, 4, 5)가 전부 끝날 때까지 기다렸다가 출력합니다. 그동안 inorder(1) 의 실행은 멈춰 있고, 그 상태는 5주차에서 배운 호출 스택에 보관됩니다. 이 스택이 4절에서 중요한 역할을 합니다.
같은 방법으로 전위와 후위를 직접 추적해 보세요. 전위는 1 이 맨 처음에, 후위는 맨 마지막에 나옵니다. 루트가 언제 나오는지가 세 순회를 구분하는 가장 빠른 방법입니다.
2.4 세 순회는 각각 어디에 쓰나
세 순회가 “결과 순서만 다른 장난”이 아닙니다. 하는 일이 다릅니다.
| 순회 | 성질 | 쓰는 곳 |
|---|---|---|
| 전위 | 부모를 자식보다 먼저 만난다 | 폴더 구조 출력(tree 명령), 트리 복사, 트리를 파일에 저장 |
| 중위 | (BST에서) 정렬된 순서로 만난다 | 5절에서 확인합니다 |
| 후위 | 자식을 부모보다 먼저 만난다 | 트리 해제, 폴더 크기 합산(du 명령), 수식 계산 |
“자식을 부모보다 먼저”가 왜 필요한지는 이 절 끝에서 직접 겪어 봅니다.
2.5 재귀로 구하는 트리 정보
순회와 똑같은 뼈대로 트리에 관한 여러 값을 구할 수 있습니다. 노드 개수를 봅시다.
/* 노드 개수: 왼쪽 개수 + 오른쪽 개수 + 나(1) */
int count_nodes(const TNode *root) {
if (root == NULL) return 0;
return 1 + count_nodes(root->left) + count_nodes(root->right);
}
“트리의 노드 수 = 1(나) + 왼쪽 부분트리의 노드 수 + 오른쪽 부분트리의 노드 수.” 1.1절의 정의 문장을 그대로 코드로 옮긴 것입니다. 빈 트리는 0개입니다.
높이도 같습니다.
/* 높이: 더 큰 부분트리 높이 + 1 (빈 트리는 -1, 잎은 0) */
int tree_height(const TNode *root) {
if (root == NULL) return -1;
int lh = tree_height(root->left);
int rh = tree_height(root->right);
return 1 + (lh > rh ? lh : rh);
}
여기서 빈 트리의 높이가 −1인 이유가 나옵니다. 잎 노드의 높이는 0이어야 합니다. 잎의 두 자식은 빈 트리이니, 1 + max(빈, 빈) 이 0이 되려면 빈 트리는 −1이어야 합니다. 정의를 그렇게 정하면 코드에 예외 처리가 하나도 필요 없습니다.
lh > rh ? lh : rh 는 3주차의 삼항 연산자로, “둘 중 큰 값”입니다.
2.6 트리를 화면에 그리기
출력 맨 위의 “트리 모양”은 이 함수가 만듭니다.
/* 트리를 옆으로 눕혀서 시각화 (오른쪽 -> 루트 -> 왼쪽 순으로 출력) */
void tree_print(const TNode *root, int depth) {
if (root == NULL) return;
tree_print(root->right, depth + 1);
printf("%*s%d\n", depth * 4, "", root->data);
tree_print(root->left, depth + 1);
}
트리를 위에서 아래로 그리려면 각 노드의 가로 위치를 미리 계산해야 해서 복잡합니다. 대신 트리를 왼쪽으로 90도 눕혀서 그립니다. 오른쪽 자식이 위에, 왼쪽 자식이 아래에 오고, 깊이만큼 들여씁니다. 이 함수는 사실 중위 순회를 오른쪽부터 한 것입니다(오른쪽 → 나 → 왼쪽).
printf("%*s%d\n", depth * 4, "", root->data) 의 %*s 는 2주차에서 본 폭 지정의 변형입니다. * 자리에 인자로 준 숫자(depth * 4)만큼의 폭으로 빈 문자열 "" 을 찍으니, 결국 공백을 depth * 4 칸 찍는 셈입니다. 깊이 2인 노드는 8칸 들여쓰기가 됩니다.
6 ← 깊이 2, 3의 오른쪽 자식
3 ← 깊이 1
1 ← 루트 (깊이 0)
5 ← 2의 오른쪽
2
4 ← 2의 왼쪽
고개를 왼쪽으로 기울여서 보면 원래 트리 그림이 됩니다. 이 출력 방식은 이번 주 내내 쓰이니 읽는 법을 익혀 두세요. 위쪽이 오른쪽 자식, 아래쪽이 왼쪽 자식입니다.
2.7 해제는 반드시 후위 순회
트리의 노드는 전부 malloc 으로 만들었으니 free 해야 합니다. 노드 여섯 개를 free 하는 순서가 중요할까요?
/* 트리 해제: 반드시 후위 순회로! (자식 먼저, 나는 나중에) */
void tree_free(TNode *root) {
if (root == NULL) return;
tree_free(root->left);
tree_free(root->right);
free(root); /* 자식을 다 지운 뒤에 나를 해제 */
}
이것이 후위 순회입니다. 왼쪽을 다 지우고, 오른쪽을 다 지우고, 마지막에 나를 지웁니다.
실험: 전위 순회로 지우면?
free(root) 를 맨 위로 올려서 전위 순회로 만들어 봅시다. 결과가 뻔해 보이지만, 무엇이 어떻게 잘못되는지 세 가지 도구로 확인해 보겠습니다. 이 도구들은 앞으로 트리 코드를 짤 때마다 쓰게 됩니다.
void tree_free_wrong(TNode *r) {
if (r == NULL) return;
free(r); /* 나를 먼저 지우고 */
tree_free_wrong(r->left); /* 지운 나의 left 를 읽는다?! */
tree_free_wrong(r->right);
}
도구 1: 컴파일러. 컴파일하는 순간 GCC 13이 잡아냅니다.
$ gcc -Wall -Wextra -std=c11 -g prefree.c -o prefree
prefree.c: In function ‘tree_free_wrong’:
prefree.c:2:99: warning: pointer ‘r’ used after ‘free’ [-Wuse-after-free]
prefree.c:2:47: note: call to ‘free’ here
“free 한 뒤에 포인터 r 을 썼다”는 경고입니다. 7주차에서 배운 해제 후 사용(use-after-free) 이고, -Wall 이 켜 주는 -Wuse-after-free 경고가 이 단순한 경우를 컴파일 단계에서 알려 줍니다. 1주차에서 “경고 0개”를 목표로 하라고 한 이유가 이런 데 있습니다.
도구 2: 그냥 실행. 경고를 무시하고 실행하면 어떻게 될까요?
$ ./prefree
세그멘테이션 오류 (코어 덤프됨)
$ echo $?
139
죽었습니다. 하지만 이건 운이 좋은 경우입니다. free 된 메모리는 곧바로 지워지는 게 아니라서, 어떤 날은 멀쩡히 돌아가고 어떤 날은 죽습니다. 그래서 “실행해 봤더니 됐다”는 아무 증거가 되지 않습니다.
도구 3: Valgrind. 7주차에서 배운 대로 정확한 위치를 짚어 줍니다.
$ valgrind ./prefree
==315240== Invalid read of size 8
==315240== at 0x109343: tree_free_wrong (prefree.c:2)
==315240== by 0x1093AD: main (prefree.c:5)
==315240== Address 0x4aac048 is 8 bytes inside a block of size 24 free'd
==315240== at 0x484988F: free (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==315240== by 0x10933E: tree_free_wrong (prefree.c:2)
...
==315240== ERROR SUMMARY: 6 errors from 6 contexts (suppressed: 0 from 0)
“24바이트짜리 블록(우리 TNode)의 8바이트 안쪽을 읽었는데, 그 블록은 이미 free 됐다.” 8바이트 안쪽은 정확히 left 필드의 위치입니다(int data 4바이트 + 패딩 4바이트 다음). free(r) 뒤에 r->left 를 읽은 것을 바이트 단위로 짚은 것입니다.
AddressSanitizer(-fsanitize=address, 4주차에서 배운 그것)도 같은 것을 heap-use-after-free 라는 이름으로 잡습니다.
정리하면, 트리 해제는 후위 순회입니다. 루트를 먼저 지우면 자식들의 주소를 잃습니다. 10주차 연결 리스트에서 “next 를 먼저 백업하고 free” 했던 것과 같은 원리이고, 트리에서는 재귀 순서가 그 백업 역할을 합니다.
이 절의 예제는 마지막에 tree_free(root) 로 정리하므로 Valgrind 로 돌리면 누수 0, 오류 0입니다.
$ valgrind --leak-check=full ./build/binary_tree_basic
...
==306412== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
3. 레벨 순서 순회: 큐의 재등장
3.1 깊이 우선과 너비 우선
2절의 세 순회는 모두 한 가지를 끝까지 파고든 뒤 돌아옵니다. 그래서 깊이 우선(depth-first) 이라고 부릅니다. 그런데 트리를 층별로 보고 싶을 때가 있습니다. 조직도에서 “사장 → 임원들 → 부장들” 순서로 읽는 것처럼요. 이것이 레벨 순서 순회(level-order), 또는 너비 우선(breadth-first) 순회입니다.
재귀로는 이게 잘 안 됩니다. 재귀는 본능적으로 아래로 파고들기 때문입니다. 대신 11주차의 큐가 답입니다. 아이디어는 이렇습니다.
- 루트를 줄(큐)에 세운다.
- 줄 맨 앞 사람을 꺼내 방문하고, 그 사람의 자식들을 줄 맨 뒤에 세운다.
- 줄이 빌 때까지 2를 반복한다.
자식을 뒤에 세우니, 같은 층 노드들이 다 나간 뒤에야 다음 층이 나옵니다.
3.2 코드
examples/level_order.c 는 11주차의 연결 리스트 큐를 그대로 가져와 씁니다. 다만 큐에 담는 것이 정수가 아니라 트리 노드의 포인터입니다.
/* ---------- 노드 포인터를 담는 연결 리스트 큐 (11주차 재사용) ---------- */
typedef struct QNode {
TNode *tree_node;
struct QNode *next;
} QNode;
typedef struct {
QNode *head, *tail;
} Queue;
큐 노드(QNode)와 트리 노드(TNode)를 헷갈리지 마세요. 큐 노드는 “줄에 선 사람”이고, 그 안의 tree_node 가 “그 사람이 가리키는 트리 노드”입니다. 큐 노드는 줄에서 나갈 때 free 되지만 트리 노드는 그대로 남습니다.
void q_push(Queue *q, TNode *tn) {
QNode *n = malloc(sizeof(QNode));
if (n == NULL) exit(1);
n->tree_node = tn;
n->next = NULL;
if (q->tail == NULL) q->head = q->tail = n;
else { q->tail->next = n; q->tail = n; }
}
TNode *q_pop(Queue *q) {
if (q->head == NULL) return NULL;
QNode *n = q->head;
TNode *tn = n->tree_node;
q->head = n->next;
if (q->head == NULL) q->tail = NULL; /* 11주차의 그 규칙! */
free(n);
return tn;
}
q_pop 의 if (q->head == NULL) q->tail = NULL; 은 11주차에서 “연결 리스트 큐의 단골 버그”로 다룬 그 줄입니다. 마지막 노드를 꺼냈는데 tail 이 지워진 노드를 계속 가리키면, 다음 q_push 가 해제된 메모리에 씁니다. 이 줄이 없으면 이 예제도 Valgrind 에서 Invalid write 가 납니다.
/* ---------- 레벨 순서 순회 ---------- */
void level_order(TNode *root) {
if (root == NULL) return;
Queue q;
q_init(&q);
q_push(&q, root); /* 루트부터 시작 */
while (!q_is_empty(&q)) {
TNode *node = q_pop(&q);
printf("%d ", node->data);
/* 내 자식들을 줄 끝에 세운다 */
if (node->left != NULL) q_push(&q, node->left);
if (node->right != NULL) q_push(&q, node->right);
}
}
재귀가 하나도 없습니다. while 반복문 하나와 큐뿐입니다. 이 예제의 트리는 노드 8개입니다.
1
/ \
2 3
/ \ / \
4 5 6 7
/
8
큐의 상태를 한 단계씩 적어 보면 왜 층별로 나오는지 보입니다. [ ] 안이 큐이고 왼쪽이 앞입니다.
| 단계 | 꺼낸 노드(출력) | 자식을 넣은 뒤의 큐 |
|---|---|---|
| 시작 | [1] |
|
| 1 | 1 | [2 3] |
| 2 | 2 | [3 4 5] |
| 3 | 3 | [4 5 6 7] |
| 4 | 4 | [5 6 7 8] |
| 5 | 5 | [6 7 8] |
| 6 | 6 | [7 8] |
| 7 | 7 | [8] |
| 8 | 8 | [ ] → 끝 |
$ ./build/level_order
=== 레벨 순서 순회 (BFS) ===
1 2 3 4 5 6 7 8
=== 층별로 나눠서 ===
레벨 0: 1
레벨 1: 2 3
레벨 2: 4 5 6 7
레벨 3: 8
깊이 우선(재귀) vs 너비 우선(큐):
- 전위 순회였다면: 1 2 4 8 5 3 6 7 (한 가지 끝까지)
- 레벨 순서는 : 1 2 3 4 5 6 7 8 (층층이)
용도: 최단 경로(층 수 = 거리), 트리를 층별로 출력/직렬화
“층별로 나눠서” 출력하는 level_order_by_line 은 작은 요령을 하나 더 씁니다. 어떤 층을 시작할 때 큐에 들어 있는 노드 수가 곧 그 층의 노드 수입니다. 그 수만큼만 꺼내면서 다음 층 노드를 세고, 다 꺼내면 줄을 바꿉니다.
int count_this = 1; /* 이번 층 노드 수 (처음엔 루트 하나) */
while (!q_is_empty(&q)) {
printf("레벨 %d: ", level);
int count_next = 0;
for (int i = 0; i < count_this; i++) {
TNode *node = q_pop(&q);
printf("%d ", node->data);
if (node->left) { q_push(&q, node->left); count_next++; }
if (node->right) { q_push(&q, node->right); count_next++; }
}
printf("\n");
count_this = count_next;
level++;
}
3.3 실험: 큐 대신 스택을 쓰면?
level_order 에서 큐를 11주차의 스택으로 바꾸면 어떻게 될까요? 넣는 순서(왼쪽, 오른쪽)는 그대로 두고 q_push 를 push, q_pop 을 pop 으로 바꾼 것입니다(dfsstack.c).
$ ./dfsstack
큐 대신 스택 (push 순서 그대로 left, right): 1 3 7 6 2 5 4 8
층별이 아니라 한 가지를 끝까지 파고듭니다. 1 → 3 → 7 → 6, 그다음 2 → 5 → 4 → 8. 오른쪽 자식이 먼저 나오는 것만 빼면 전위 순회입니다(오른쪽이 먼저 나오는 이유는 4절에서 봅니다).
자료구조 하나를 바꿨을 뿐인데 순회 방식이 바뀝니다. 큐(먼저 넣은 것 먼저)는 너비 우선, 스택(나중에 넣은 것 먼저)은 깊이 우선. 14주차 그래프에서 DFS 와 BFS 를 배울 때 이 관계가 그대로 다시 나옵니다. 그리고 이 실험은 다음 절로 가는 다리입니다. “스택을 쓰면 깊이 우선이 된다”는 것은, 재귀 없이도 전위 순회를 만들 수 있다는 뜻이니까요.
4. 재귀를 스택으로 바꾸기
4.1 왜 바꾸나
2절의 재귀 순회는 짧고 아름답습니다. 그런데 문제가 하나 있습니다. 재귀는 호출이 깊어질 때마다 호출 스택에 프레임을 하나씩 쌓고, 호출 스택의 크기는 정해져 있습니다(5주차에서 약 8MB, 무한 재귀가 52만 번쯤에서 죽는 것을 봤습니다). 트리의 높이가 곧 재귀의 깊이이므로, 아주 높은 트리에서는 재귀 순회가 죽습니다.
정말 그런지 확인해 봅시다. 노드 100만 개를 오른쪽으로만 이어 붙인 사슬 모양 트리(높이 999,999)를 만들고, 재귀와 반복문으로 노드 수를 세어 봅니다(deep.c).
$ ./deep 100000 r
사슬 노드 100000개, 재귀로 세기: 100000개
$ ./deep 1000000 r
사슬 노드 1000000개, 재귀로 세기: 세그멘테이션 오류 (코어 덤프됨)
$ echo $?
139
$ ./deep 1000000 i
사슬 노드 1000000개, 반복문으로 세기: 1000000개
10만 개는 되고 100만 개는 죽습니다. 5주차에서 본 스택 오버플로 그대로입니다. 반복문은 힙 메모리를 쓰거나 아예 스택을 안 쓰니 문제없습니다.
“높이 100만인 트리가 실제로 있나?” 싶겠지만, 5절에서 보게 될 정렬된 입력은 BST 를 정확히 이런 사슬로 만듭니다. 그리고 순회를 “중간에 멈췄다가 이어서” 하고 싶을 때(한 번에 한 노드씩 꺼내 주는 이터레이터)도 재귀로는 불가능합니다. 재귀는 끝날 때까지 멈추지 않으니까요.
11주차에서 “모든 재귀는 스택 + 반복문으로 바꿀 수 있다”고 했습니다. 이제 그 약속을 지킬 차례입니다.
4.2 전위 순회: 오른쪽을 먼저 넣는다
examples/traversal_iterative.c 는 11주차의 배열 스택을 씁니다.
/* ---------- 노드 포인터 스택 (11주차 배열 스택 재사용) ---------- */
#define MAX_DEPTH 64
typedef struct {
TNode *data[MAX_DEPTH];
int top;
} Stack;
void s_init(Stack *s) { s->top = -1; }
int s_is_empty(const Stack *s) { return s->top < 0; }
TNode *s_pop(Stack *s) { return s->data[s->top--]; }
/* 가득 찬 배열에 push하면 data[64]에 쓰는데, 그 자리는 바로 뒤의 top이다.
* top이 엉뚱한 값으로 덮여 순회가 조용히 잘못된 결과를 낸다 (실제로 겪음).
* 넘치면 멈추게 하고, 큰 트리는 11주차의 동적 배열 스택을 쓴다. */
void s_push(Stack *s, TNode *n) {
if (s->top + 1 >= MAX_DEPTH) {
fprintf(stderr, "스택 넘침: 깊이가 %d를 넘는 트리입니다\n", MAX_DEPTH);
exit(1);
}
s->data[++s->top] = n;
}
s_push 의 검사는 이 글을 쓰면서 추가했습니다. 무슨 일이 있었는지는 4.4절에서 봅니다.
전위 순회의 반복문 버전입니다.
/* ---------- 반복문 전위 순회 ----------
* 재귀 호출 대신 "나중에 방문할 노드"를 스택에 기억.
* 오른쪽을 먼저 push해야 왼쪽이 먼저 pop된다 (LIFO!) */
void preorder_iter(TNode *root) {
if (root == NULL) return;
Stack s;
s_init(&s);
s_push(&s, root);
while (!s_is_empty(&s)) {
TNode *node = s_pop(&s);
printf("%d ", node->data);
if (node->right != NULL) s_push(&s, node->right); /* 나중에 */
if (node->left != NULL) s_push(&s, node->left); /* 먼저! */
}
}
3절의 레벨 순회와 모양이 똑같고, 큐가 스택으로 바뀌었습니다. 딱 하나 다른 점은 오른쪽을 먼저 push 한다는 것입니다. 스택은 나중에 넣은 것이 먼저 나오니(LIFO), 먼저 방문하고 싶은 왼쪽을 나중에 넣어야 먼저 나옵니다. 3.3절 실험에서 왼쪽을 먼저 넣었더니 오른쪽이 먼저 나온 이유가 이것입니다.
이 예제의 트리로 스택 상태를 따라가 봅시다.
4
/ \
2 6
/ \ / \
1 3 5 7
| 꺼낸 노드(출력) | push 뒤의 스택 (오른쪽이 꼭대기) |
|---|---|
[4] |
|
| 4 | [6 2] (오른쪽 6을 먼저, 왼쪽 2를 나중에) |
| 2 | [6 3 1] |
| 1 | [6 3] |
| 3 | [6] |
| 6 | [7 5] |
| 5 | [7] |
| 7 | [ ] |
4 2 1 3 6 5 7. 재귀 전위 순회와 같습니다.
4.3 중위 순회: 왼쪽 경로를 쌓는다
중위 순회는 조금 더 생각이 필요합니다. “나”를 왼쪽 부분트리 다음에 방문해야 하므로, 나를 꺼내기 전에 왼쪽으로 갈 수 있는 데까지 내려가야 합니다.
/* ---------- 반복문 중위 순회 ----------
* "왼쪽 끝까지 내려가며 경로를 스택에 쌓고,
* pop하면서 방문하고, 오른쪽으로 한 발" */
void inorder_iter(TNode *root) {
Stack s;
s_init(&s);
TNode *cur = root;
while (cur != NULL || !s_is_empty(&s)) {
while (cur != NULL) { /* 1. 왼쪽 끝까지 push */
s_push(&s, cur);
cur = cur->left;
}
cur = s_pop(&s); /* 2. 방문 */
printf("%d ", cur->data);
cur = cur->right; /* 3. 오른쪽으로 */
}
}
리듬은 세 박자입니다. 왼쪽 끝까지 쌓기 → 하나 꺼내 방문 → 오른쪽으로 한 발. 오른쪽으로 한 발 간 뒤에는 다시 그 노드의 왼쪽 끝까지 쌓습니다.
| 동작 | cur | 스택 | 출력 |
|---|---|---|---|
| 4, 2, 1 을 왼쪽으로 내려가며 push | NULL | [4 2 1] |
|
| pop → 방문, 오른쪽으로 | 1의 오른쪽 = NULL | [4 2] |
1 |
| 쌓을 것 없음. pop → 방문, 오른쪽으로 | 3 | [4] |
2 |
| 3 push, 왼쪽 없음. pop → 방문, 오른쪽으로 | NULL | [4] |
3 |
| pop → 방문, 오른쪽으로 | 6 | [ ] |
4 |
| 6, 5 push. pop → 방문 | NULL | [6] |
5 |
| pop → 방문, 오른쪽으로 | 7 | [ ] |
6 |
| 7 push, pop → 방문 | NULL | [ ] |
7 |
바깥 while 의 조건이 cur != NULL || !s_is_empty(&s) 인 이유도 이 표에서 보입니다. 스택이 비었어도(4 를 꺼낸 직후) cur 이 6 을 가리키고 있으면 아직 할 일이 남았습니다.
$ ./build/traversal_iterative
=== 전위 순회: 재귀 vs 스택 ===
재귀 : 4 2 1 3 6 5 7
반복문: 4 2 1 3 6 5 7
=== 중위 순회: 재귀 vs 스택 ===
재귀 : 1 2 3 4 5 6 7
반복문: 1 2 3 4 5 6 7
같은 결과! 재귀의 '함수 호출 스택'을 '내가 만든 스택'으로
바꿨을 뿐입니다. 전위는 오른쪽을 먼저 push하는 것(LIFO 보정),
중위는 '왼쪽 경로 쌓기-pop-오른쪽 한 발' 리듬이 핵심입니다.
순회를 반복문으로
재귀 버전에서 “inorder(1) 이 왼쪽이 끝나기를 기다리며 호출 스택에 남아 있던 것”(2.3절)이, 반복문 버전에서는 “4 가 우리 스택 바닥에 남아 있는 것”과 정확히 대응합니다. 재귀가 컴파일러에게 맡겼던 스택을 우리가 직접 들고 있는 것뿐입니다.
4.4 실험: 이 스택은 몇 층까지 버틸까
이 예제의 스택은 MAX_DEPTH, 즉 64칸짜리 고정 배열입니다. 중위 순회는 왼쪽 경로를 전부 쌓으므로, 왼쪽으로만 65개 이어진 사슬을 주면 65번째 push 에서 배열을 넘칩니다. 검사를 넣기 전의 원래 코드(s->data[++s->top] = n; 한 줄)로 해 보면 이렇습니다(deepiter2.c).
$ ./deepiter2 64
왼쪽 사슬 64개, inorder_iter: 64 63 62 61 60 59 58 57 ... 3 2 1
$ ./deepiter2 65
왼쪽 사슬 65개, inorder_iter:
$ echo $?
0
65개에서는 아무것도 출력하지 않고 종료 코드 0으로 조용히 끝납니다. 오류 메시지도, 세그멘테이션 오류도 없습니다. 이유는 구조체의 배치에 있습니다.
typedef struct {
TNode *data[MAX_DEPTH]; /* data[0] ~ data[63] */
int top; /* data[64] 자리에 바로 top 이 있다 */
} Stack;
data[64] 에 쓰는 것은 곧 top 을 덮어쓰는 것입니다. top 에 트리 노드의 주소가 숫자로 들어가고, 그 뒤로 스택은 엉망이 됩니다. 4주차에서 배열 범위를 넘겨 쓰면 옆 변수가 바뀌던 실험의 트리 버전입니다. AddressSanitizer 로 돌리면 정확한 줄을 알려 줍니다.
$ gcc -std=c11 -g -fsanitize=address deepiter2.c -o deepiter2_asan
$ ./deepiter2_asan 100
==321581==ERROR: AddressSanitizer: SEGV on unknown address 0x000000000000 ...
#0 ... in inorder_iter ../examples/traversal_iterative.c:75
그래서 예제의 s_push 에 넘침 검사를 넣었습니다. 지금은 넘치면 메시지를 내고 멈춥니다.
$ ./deepiter2 65
왼쪽 사슬 65개, inorder_iter: 스택 넘침: 깊이가 64를 넘는 트리입니다
$ echo $?
1
“조용히 틀린 결과”보다 “시끄럽게 멈추는 것”이 항상 낫습니다. 제대로 된 해결은 11주차의 동적 배열 스택(가득 차면 realloc 으로 두 배)을 쓰는 것이고, 연습 문제로 남겨 두었습니다. 4.1절의 사슬 100만 개도 그 스택이면 순회할 수 있습니다.
5. 이진 탐색 트리 (BST): 규칙 하나가 만드는 마법
5.1 규칙
지금까지의 트리는 값이 아무 데나 놓여 있었습니다. 이제 규칙을 하나 더합니다.
모든 노드에서: 왼쪽 부분트리의 모든 값 < 나 < 오른쪽 부분트리의 모든 값
이 규칙을 지키는 이진 트리를 이진 탐색 트리(Binary Search Tree, BST) 라고 합니다. “왼쪽 자식 < 나 < 오른쪽 자식”이 아니라 왼쪽 부분트리 전체입니다. 이 차이가 7절에서 함정으로 나옵니다.
규칙 하나가 왜 마법일까요? 어떤 값을 찾는다고 해 봅시다. 루트와 비교합니다. 찾는 값이 작으면 오른쪽 부분트리에는 있을 리가 없으니 오른쪽 전체를 버리고 왼쪽으로 갑니다. 크면 왼쪽 전체를 버립니다. 한 번 비교할 때마다 후보의 절반이 사라집니다. 이것은 15주차에서 배울 이진 탐색과 같은 원리이고, BST 는 말하자면 “살아 있는 이진 탐색”입니다.
트리가 균형 잡혀 있다면(높이가 약 log₂ n 이라면) 100만 개 중 하나를 찾는 데 약 20번 비교면 됩니다. 2²⁰ ≈ 100만이니까요. 연결 리스트의 최악 100만 번과 비교해 보세요. 단, “균형 잡혀 있다면”이라는 조건이 붙습니다. 이 조건이 깨지는 것을 5.5절에서 봅니다.
5.2 삽입: 트리 코드의 표준 문형
examples/bst_insert_search.c 의 삽입 함수입니다. 이번 주에서 가장 중요한 코드 한 덩이입니다.
/* 삽입: 자리를 찾아 내려가다 빈 곳(NULL)에 붙인다.
* "부분트리의 새 루트를 반환"하는 재귀 패턴 - 트리 코드의 표준 문형 */
TNode *bst_insert(TNode *root, int data) {
if (root == NULL) {
return node_create(data); /* 빈 자리 발견: 여기가 내 자리 */
}
if (data < root->data) {
root->left = bst_insert(root->left, data);
} else if (data > root->data) {
root->right = bst_insert(root->right, data);
}
/* 같으면 무시 (중복 없는 BST) */
return root; /* 이 부분트리의 루트는 그대로 나 */
}
한 줄씩 봅시다.
- 반환형이
TNode *입니다. 이 함수는 “값을 넣은 뒤의 이 부분트리의 루트“를 돌려줍니다. 빈 트리에 넣으면 새 노드가 루트가 되고, 비어 있지 않으면 루트는 그대로입니다. if (root == NULL) return node_create(data);: 빈 자리를 찾았습니다. 새 노드를 만들어 돌려주면, 부른 쪽이 그것을 자기left나right에 붙입니다.root->left = bst_insert(root->left, data);: 이 줄이 핵심입니다. 왼쪽 부분트리에 삽입하고, 그 결과로 받은 새 루트를 다시root->left에 대입합니다. 왼쪽이 비어 있었다면 새 노드가 붙고, 아니었다면 원래 있던 노드가 그대로 다시 대입됩니다(값이 같으니 아무 변화 없음).return root;: 나는 여전히 이 부분트리의 루트입니다.
“결과를 돌려주고, 부른 쪽이 다시 대입한다.” 이 방식을 부분트리의 새 루트를 반환하는 패턴이라고 부르겠습니다. 처음에는 “왜 굳이 같은 값을 다시 대입하지?” 싶지만, 이 패턴 덕분에 부모의 포인터를 고치는 코드가 따로 필요 없습니다. 7주차에서 “함수 안에서 호출자의 포인터를 바꾸려면 이중 포인터가 필요하다”고 배웠는데, 이 패턴은 반환값으로 그 문제를 우아하게 피해 갑니다. 삭제(6절), AVL 회전(8절), 프로젝트의 AST 까지 전부 이 패턴으로 만듭니다.
그래서 부르는 쪽은 반드시 반환값을 받아야 합니다.
root = bst_insert(root, 42); /* 반환값을 다시 root 에 대입하는 것까지가 한 세트 */
실험: 반환값을 안 받으면
root = 를 빼고 부르면 어떻게 될까요(noassign.c)?
TNode *root = NULL;
bst_insert(root, 42); /* 반환값을 버림 */
printf("bst_insert(root, 42) 후 root = %p\n", (void *)root);
root = bst_insert(root, 42);
printf("root = bst_insert(root, 42) 후 root = %p, root->data = %d\n", (void *)root, root->data);
$ ./noassign
bst_insert(root, 42) 후 root = (nil)
root = bst_insert(root, 42) 후 root = 0x5c0c38f1a2d0, root->data = 42
첫 번째 호출은 노드를 만들어 돌려줬지만 아무도 받지 않았습니다. root 는 여전히 NULL 이고, 만든 노드는 주소를 잃어 누수가 됐습니다(Valgrind 로 돌리면 24바이트 definitely lost). 컴파일러는 경고하지 않습니다. 반환값을 버리는 것은 문법상 합법이니까요. 이 실수는 11절의 목록 맨 위에 올려 두었습니다.
5.3 트리가 자라는 모습
예제는 50 30 70 20 40 60 80 10 45 를 순서대로 넣습니다. 처음 네 개가 어디로 가는지 따라가 봅시다.
50 삽입: 빈 트리 → 50 이 루트
50
30 삽입: 30 < 50 → 왼쪽. 왼쪽이 비었으니 여기
50
/
30
70 삽입: 70 > 50 → 오른쪽. 비었으니 여기
50
/ \
30 70
20 삽입: 20 < 50 → 왼쪽으로. 20 < 30 → 또 왼쪽. 비었으니 여기
50
/ \
30 70
/
20
45 는 50 → 30 → 40 → (40의 오른쪽) 을 거쳐 네 단계 내려갑니다. 9개를 다 넣은 결과는 이렇습니다.
$ ./build/bst_insert_search
=== 삽입 순서: 50 30 70 20 40 60 80 10 45 ===
트리 모양:
80
70
60
50
45
40
30
20
10
=== BST의 마법: 중위 순회 = 정렬! ===
중위 순회: 10 20 30 40 45 50 60 70 80
(정렬한 적이 없는데 정렬되어 나온다)
=== 탐색: 몇 번 비교했나 ===
45 탐색: 발견 (4번 이동)
80 탐색: 발견 (3번 이동)
99 탐색: 없음 (4번 이동)
9개 노드를 다 안 뒤져도 된다. 절반씩 버리니까!
=== 최소/최대 ===
최솟값: 10 (가장 왼쪽)
최댓값: 80 (가장 오른쪽)
트리 모양은 2.6절의 눕힌 그림입니다. 바로 세우면 이렇습니다.
50
/ \
30 70
/ \ / \
20 40 60 80
/ \
10 45
5.4 중위 순회는 정렬이다
출력 가운데를 보세요. 중위 순회를 했더니 10 20 30 40 45 50 60 70 80, 정렬된 순서가 나왔습니다. 정렬 알고리즘을 쓴 적이 없는데도요.
이유는 규칙과 순회 순서를 나란히 놓으면 보입니다.
- BST 규칙: 왼쪽 부분트리 < 나 < 오른쪽 부분트리
- 중위 순회: 왼쪽 부분트리 → 나 → 오른쪽 부분트리
“작은 것들 → 나 → 큰 것들” 순서로 방문하니, 모든 노드에서 이 관계가 지켜지면 전체가 오름차순이 됩니다. 이 성질은 이번 주 내내 “트리가 아직 BST 인가”를 확인하는 도구로 씁니다. 삭제나 회전을 한 뒤 중위 순회가 여전히 정렬돼 있으면 규칙이 살아 있는 것입니다.
최솟값과 최댓값도 쉽습니다. 규칙상 가장 작은 값은 왼쪽으로만 끝까지 내려간 곳, 가장 큰 값은 오른쪽으로만 끝까지 내려간 곳에 있습니다.
/* 최솟값: 왼쪽으로만 끝까지 (BST 규칙상 가장 왼쪽이 최소) */
TNode *bst_min(TNode *root) {
if (root == NULL) return NULL;
while (root->left != NULL) root = root->left;
return root;
}
재귀가 아니라 반복문입니다. 한 방향으로만 가는 것은 반복문이 더 자연스럽습니다. root = root->left 로 포인터를 한 칸씩 옮기는 것은 10주차 리스트 순회의 cur = cur->next 와 같습니다.
5.5 탐색: 몇 번 만에 찾나
/* 탐색: 크면 오른쪽, 작으면 왼쪽. 절반씩 버리는 이진 탐색! */
TNode *bst_search(TNode *root, int target, int *steps) {
(*steps)++;
if (root == NULL) return NULL; /* 없다 */
if (target == root->data) return root;
if (target < root->data) {
return bst_search(root->left, target, steps);
}
return bst_search(root->right, target, steps);
}
steps 는 몇 개의 노드를 거쳤는지 세려고 6주차 방식으로 포인터를 넘겨 받은 카운터입니다.
45 를 찾는 과정을 한 단계씩 적으면 이렇습니다.
| 단계 | 현재 노드 | 비교 | 다음 |
|---|---|---|---|
| 1 | 50 | 45 < 50 | 왼쪽으로 (70, 60, 80 은 볼 필요 없음) |
| 2 | 30 | 45 > 30 | 오른쪽으로 (20, 10 은 볼 필요 없음) |
| 3 | 40 | 45 > 40 | 오른쪽으로 |
| 4 | 45 | 같다 | 발견 |
세 번의 비교로 다섯 개 노드(70, 60, 80, 20, 10)를 한 번도 보지 않고 걸러 냈습니다. 없는 값 99 는 50 → 70 → 80 → NULL 로 네 단계 만에 “없다”가 확정됩니다. 리스트라면 아홉 개를 전부 봐야 없다고 말할 수 있습니다. 출력을 보면 45 는 4번(50, 30, 40, 45), 80 은 3번(50, 70, 80) 만에 찾았고, 없는 값 99 는 4번(50, 70, 80, 그리고 NULL) 만에 “없다”고 결론 냅니다. 9개 노드 중 최대 4개만 봤습니다. 비교 횟수의 상한이 트리의 높이 + 1 입니다.
실험: 정렬된 값을 넣으면 트리는 어떻게 생길까
그럼 높이는 얼마나 될까요? 넣는 순서에 따라 다릅니다. 같은 값들을 정렬된 순서로 넣은 경우와 섞어서 넣은 경우의 높이를 비교해 보겠습니다(chain.c, 시간은 이 컴퓨터에서 잰 값입니다).
$ ./chain
n= 15 정렬 입력: 높이 14 (0.0 ms) 섞은 입력: 높이 7 (0.0 ms) log2(n)=3.9
n= 1000 정렬 입력: 높이 999 (2.9 ms) 섞은 입력: 높이 24 (0.1 ms) log2(n)=10.0
n=20000 정렬 입력: 높이 19999 (964.6 ms) 섞은 입력: 높이 33 (3.1 ms) log2(n)=14.3
정렬된 입력에서는 높이가 n − 1입니다. 1, 2, 3, … 을 넣으면 매번 “나보다 크다 → 오른쪽”이라 오른쪽으로만 자라서, 트리가 아니라 사슬이 됩니다. 4.1절에서 재귀를 죽였던 바로 그 모양입니다.
1
\
2
\
3
\
...
이러면 탐색은 리스트와 똑같은 O(n) 이고, 삽입도 매번 사슬 끝까지 내려가야 해서 n 개를 넣는 데 O(n²) 입니다. 20,000개에 1초 가까이 걸린 이유입니다. 섞어 넣으면 높이 33으로 log₂ n 의 두 배 정도이고, 삽입은 3ms 입니다. 같은 자료구조, 같은 값인데 넣는 순서가 300배 차이를 만들었습니다.
그런데 정렬된 데이터는 실무에서 아주 흔합니다. 시간순 로그, 자동 증가하는 ID, 이미 정렬된 파일. 그래서 “삽입 순서와 상관없이 균형을 유지하는” 트리가 필요하고, 그것이 8절의 AVL 트리입니다. 그 전에 삭제부터 끝내야 합니다.
6. BST 삭제: 세 가지 경우
6.1 왜 삭제가 어려운가
삽입은 항상 잎에 붙이면 끝입니다. 하지만 삭제는 트리 한가운데 노드를 뺄 수도 있습니다. 노드를 빼고 나서도 “왼쪽 < 나 < 오른쪽” 규칙이 모든 노드에서 유지돼야 합니다. 빼는 노드의 자식이 몇 개인지에 따라 세 가지 경우로 나뉩니다.
| 경우 | 상황 | 처리 |
|---|---|---|
| 1 | 자식이 없다 (잎) | 그냥 뗀다 |
| 2 | 자식이 하나 | 그 자식이 내 자리를 물려받는다 |
| 3 | 자식이 둘 | 후속자(오른쪽 부분트리의 최솟값)의 값을 가져오고, 후속자를 대신 지운다 |
examples/bst_delete.c 의 코드입니다. 5.2절의 패턴 그대로, “삭제한 뒤의 이 부분트리의 루트”를 돌려줍니다.
/* 삭제: "부분트리의 새 루트를 반환" 패턴 */
TNode *bst_delete(TNode *root, int data) {
if (root == NULL) return NULL; /* 없는 값: 아무 일 없음 */
if (data < root->data) {
root->left = bst_delete(root->left, data);
} else if (data > root->data) {
root->right = bst_delete(root->right, data);
} else {
/* 찾았다! 세 가지 경우로 나뉜다 */
if (root->left == NULL && root->right == NULL) {
/* 경우 1: 잎 - 그냥 제거 */
free(root);
return NULL;
}
if (root->left == NULL) {
/* 경우 2a: 오른쪽 자식만 - 자식이 승계 */
TNode *child = root->right;
free(root);
return child;
}
if (root->right == NULL) {
/* 경우 2b: 왼쪽 자식만 */
TNode *child = root->left;
free(root);
return child;
}
/* 경우 3: 자식 둘 - 후속자(오른쪽의 최솟값)로 대체 */
TNode *successor = bst_min(root->right);
root->data = successor->data; /* 값만 복사하고 */
root->right = bst_delete(root->right, successor->data);
/* 후속자 노드를 재귀 삭제 (후속자는 왼쪽 자식이 없으니
* 경우 1 또는 2로 끝난다 - 무한 재귀 없음!) */
}
return root;
}
앞부분은 삽입과 똑같습니다. 값을 찾아 왼쪽이나 오른쪽으로 내려가며, 결과를 다시 대입합니다. 값을 찾은 else 안이 본론입니다.
6.2 경우 1과 2: 예제로
예제의 시작 트리입니다.
50
/ \
30 70
/ \ / \
20 40 60 80
/
35
경우 1: 20 삭제. 20은 잎입니다. free 하고 NULL 을 돌려주면, 부른 쪽(30 의 처리)에서 root->left = NULL 이 되어 연결이 끊깁니다.
경우 2: 40 삭제. 40은 왼쪽 자식 35 하나만 있습니다. 40을 free 하고 35를 돌려주면, 30 의 right 가 35를 가리키게 됩니다. 35가 40의 자리를 물려받은 것입니다. 10주차 리스트에서 노드를 지울 때 “앞 노드의 next 를 뒷 노드로 건너뛰게” 했던 것과 같습니다. 반환값 패턴이 그 건너뛰기를 해 줍니다.
root = bst_delete(root, 40) 한 줄이 실제로 어떤 호출을 거치는지 따라가 봅시다.
bst_delete(50, 40) 40 < 50 → root->left = bst_delete(30, 40) 의 결과
bst_delete(30, 40) 40 > 30 → root->right = bst_delete(40, 40) 의 결과
bst_delete(40, 40) 찾았다. 왼쪽 자식 35 만 있으니 경우 2b
child = 35 를 기억, free(40), return 35
30->right = 35 ← 30 의 오른쪽이 40 에서 35 로 바뀐다
return 30
50->left = 30 ← 값이 같으니 아무 변화 없음
return 50
root = 50 ← 루트도 그대로
실제로 포인터가 바뀐 곳은 30->right 딱 하나입니다. 나머지 대입은 같은 값을 다시 쓰는 것이고, 그래서 어느 깊이에서 삭제가 일어나든 코드가 같습니다.
$ ./build/bst_delete
=== 시작 트리 ===
80
70
60
50
40
35
30
20
중위: 20 30 35 40 50 60 70 80
>>> 20 삭제 (경우 1: 잎)
80
70
60
50
40
35
30
중위: 30 35 40 50 60 70 80
>>> 40 삭제 (경우 2: 자식 하나 - 35가 승계)
80
70
60
50
35
30
중위: 30 35 50 60 70 80
삭제할 때마다 중위 순회를 찍어 정렬 순서가 유지되는지 확인합니다. 5.4절에서 말한 “BST 인지 확인하는 도구”입니다.
6.3 경우 3: 후속자로 바꿔치기
50 삭제. 루트이고 자식이 둘입니다. 50을 그냥 떼면 30과 70 두 부분트리가 붕 뜹니다. 누가 50의 자리를 이어받아야 규칙이 유지될까요?
새 루트는 “왼쪽 부분트리 전부보다 크고, 오른쪽 부분트리 전부보다 작아야” 합니다. 그런 값이 정확히 두 개 있습니다. 왼쪽 부분트리의 최댓값(50 바로 아래 값)과 오른쪽 부분트리의 최솟값(50 바로 위 값). 정렬 순서 30 35 50 60 70 80 에서 50의 양옆 이웃인 35와 60입니다. 예제는 오른쪽의 최솟값, 즉 후속자(successor) 60을 씁니다.
그다음이 요령입니다. 60 노드를 50 자리로 옮기는 게 아니라, 50 노드에 값 60을 덮어쓰고, 오른쪽 부분트리에서 60을 삭제합니다.
TNode *successor = bst_min(root->right); /* 60 */
root->data = successor->data; /* 50 자리에 60 을 쓴다 */
root->right = bst_delete(root->right, 60); /* 오른쪽에서 60 을 지운다 */
왜 이렇게 할까요? 후속자는 “오른쪽 부분트리에서 왼쪽으로만 끝까지 간 곳”이라 왼쪽 자식이 없습니다. 그러니 후속자를 지우는 것은 반드시 경우 1(잎)이나 경우 2(오른쪽 자식만)로 끝납니다. 경우 3이 또 경우 3을 부르는 무한 재귀가 생기지 않습니다. 이 예제에서 60은 잎이라 경우 1입니다.
>>> 50 삭제 (경우 3: 자식 둘 - 후속자 60이 루트로!)
80
70
60
35
30
중위: 30 35 60 70 80
>>> 99 삭제 (없는 값 - 아무 일 없음)
...
모든 삭제 후에도 중위 순회가 정렬 순서 = BST 규칙 유지 성공!
바로 세워 보면 60이 루트가 됐고, 70 아래에 있던 60의 자리는 비었습니다.
60
/ \
30 70
\ \
35 80
없는 값 99 를 지우면 NULL 에 도달해 아무 일도 하지 않고 돌아옵니다. 첫 줄의 if (root == NULL) return NULL; 이 그 역할입니다.
실험: 후속자 대신 선행자를 쓰면?
경우 3에서 왼쪽 부분트리의 최댓값(선행자, 여기서는 35)을 써도 규칙은 유지됩니다. 대칭이니까요. bst_min(root->right) 를 bst_max(root->left) 로, root->right = bst_delete(root->right, ...) 를 root->left = bst_delete(root->left, ...) 로 바꿔 보세요. 결과 트리의 모양은 다르지만 중위 순회는 똑같이 정렬돼 나옵니다. 어느 쪽을 쓰든 상관없고, 둘을 번갈아 쓰면 트리가 한쪽으로 덜 기웁니다.
7. 검증과 이웃 찾기
7.1 “이 트리, 진짜 BST 맞아?”
트리를 받았는데 누가 만들었는지 모릅니다. BST 규칙을 지키는지 검사하고 싶습니다. 가장 먼저 떠오르는 방법은 “각 노드에서 왼쪽 자식은 나보다 작고 오른쪽 자식은 나보다 큰지” 확인하는 것입니다. examples/bst_validate.c 에 그 순진한 버전이 있습니다.
/* ---------- 잘못된 검증 (반례가 있다!) ---------- */
int validate_naive(const TNode *root) {
if (root == NULL) return 1;
if (root->left && root->left->data >= root->data) return 0;
if (root->right && root->right->data <= root->data) return 0;
return validate_naive(root->left) && validate_naive(root->right);
}
이 코드는 틀렸습니다. 반례가 있습니다.
50
/
30
\
55
30 은 50 보다 작습니다(OK). 55 는 30 보다 큽니다(OK). 노드 하나하나만 보면 전부 합격입니다. 그런데 55 는 50 의 왼쪽 부분트리에 있습니다. 5.1절에서 강조한 “왼쪽 부분트리 전체 < 나”를 어겼습니다. 이 트리에서 55 를 찾으면 50 에서 오른쪽으로 가니 절대 못 찾습니다. BST 가 아닙니다.
문제는 각 노드가 자기 부모만 보고 조상은 안 본다는 것입니다. 55 는 “30 의 오른쪽에 있어도 되지만, 동시에 50 의 왼쪽 세계 안에 있으니 50 보다 작아야 한다”는 조건을 받아야 합니다.
7.2 허용 범위를 물려주기
해법은 조상들이 정한 허용 범위(최소, 최대) 를 아래로 물려주는 것입니다.
/* ---------- 올바른 검증: 허용 범위(min, max)를 물려준다 ---------- */
int validate_range(const TNode *root, long min, long max) {
if (root == NULL) return 1;
if (root->data <= min || root->data >= max) return 0;
return validate_range(root->left, min, root->data) &&
validate_range(root->right, root->data, max);
}
int is_bst(const TNode *root) {
return validate_range(root, LONG_MIN, LONG_MAX);
}
- 루트는 아무 제한이 없으니
(LONG_MIN, LONG_MAX)로 시작합니다.int값이 어떤 것이든 이 범위 안에 있도록long을 썼습니다. 2주차에서 본<limits.h>의 값입니다. - 왼쪽으로 가면 최대가 좁아지고, 오른쪽으로 가면 최소가 좁아집니다. 50의 왼쪽으로 가면 “50 미만”이 되고, 거기서 30의 오른쪽으로 가면 “30 초과 50 미만”이 됩니다.
- 55 는
(30, 50)범위를 벗어나므로0을 돌려줍니다.
$ ./build/bst_validate
=== 검증 ===
정상 BST: naive=통과, range=통과
함정 트리: naive=통과 <- 못 잡는다!
함정 트리: range=실패 <- 범위 검사는 잡는다
(55는 '30의 오른쪽'으론 합법이지만 '50의 왼쪽 세계'에선 불법)
&& 로 두 재귀를 이은 마지막 줄은 3주차에서 배운 단락 평가를 활용합니다. 왼쪽 검사가 실패하면 오른쪽은 아예 검사하지 않고 바로 0 입니다.
이 함정은 면접 문제로도 유명합니다. “BST 검증 함수를 짜 보세요”라고 하면 절반은 순진한 버전을 냅니다. 반례 트리 하나를 기억해 두면 평생 안 틀립니다.
7.3 이웃 찾기: 후속자와 선행자
6절에서 후속자를 “오른쪽 부분트리의 최솟값”으로 찾았습니다. 그 노드의 오른쪽 부분트리가 있을 때만 통하는 방법입니다. 오른쪽 부분트리가 없는 노드의 후속자는 어디 있을까요? 예를 들어 위 트리에서 45 의 후속자는 50 인데, 50 은 45 의 조상입니다.
루트에서 내려가면서 후보를 갱신하는 방법이 일반적입니다.
/* ---------- 후속자: 나보다 큰 것 중 최소 ----------
* 루트에서 내려가며: target보다 크면 "후보로 기억하고" 왼쪽으로,
* 작거나 같으면 오른쪽으로. */
TNode *bst_successor(TNode *root, int target) {
TNode *candidate = NULL;
while (root != NULL) {
if (root->data > target) {
candidate = root; /* 일단 후보. 더 작은 큰 값을 찾아 */
root = root->left; /* 왼쪽으로 */
} else {
root = root->right;
}
}
return candidate;
}
“나보다 큰 값을 만나면 일단 후보로 적어 두고, 더 작은 큰 값이 있는지 왼쪽으로 가서 본다.” 40 의 후속자를 찾는 과정입니다(트리는 50 30 70 20 40 60 80).
| 현재 노드 | 40 보다 큰가 |
동작 | candidate |
|---|---|---|---|
| 50 | 크다 | 후보로 기억, 왼쪽으로 | 50 |
| 30 | 작다 | 오른쪽으로 | 50 |
| 40 | 같다(크지 않다) | 오른쪽으로 | 50 |
| NULL | 끝 | 50 |
40 보다 큰 값 중 가장 작은 것은 50 입니다. 선행자는 부등호와 방향만 뒤집으면 됩니다.
=== 후속자 / 선행자 ===
정렬 순서: 20 30 40 50 60 70 80
40 : 선행자 30, 후속자 50
50 : 선행자 40, 후속자 60
80 : 선행자 70, 후속자 없음
15 : 선행자 없음, 후속자 20
80 은 가장 큰 값이라 후속자가 없고(NULL), 15 는 트리에 없는 값인데도 “15 보다 큰 것 중 최소”인 20 을 잘 찾습니다. 이 함수는 트리에 있는 값만 받는 게 아니라 어떤 값이든 그 값의 양옆 이웃을 찾아 줍니다. “이 시각 이후 첫 예약”, “이 가격 이하 최고가” 같은 질문에 쓰는 도구입니다.
8. AVL 트리: 스스로 균형을 잡는 BST
8.1 문제를 숫자로 다시 보기
5.5절에서 정렬된 입력이 BST 를 사슬로 만드는 것을 봤습니다. 그게 얼마나 큰 문제인지 한 번 더 숫자로 봅시다. 1부터 20,000까지 순서대로 넣은 뒤, 20,000을 찾는 데 몇 번 이동하는지, 그리고 모든 키를 한 번씩 찾을 때 평균 몇 번 이동하는지 잰 것입니다(steps.c). AVL 은 이 절에서 만들 트리입니다.
$ ./steps
1~20000 순서대로 삽입
삽입 시간 높이 탐색(20000) 전체 키 평균 이동
순수 BST : 252.9 ms 19999 20000번 10000.5번
AVL : 4.6 ms 14 15번 13.4번
사슬 BST 에서 20,000을 찾으려면 20,000번 이동합니다. 리스트와 똑같습니다. AVL 트리는 높이가 14라서 15번이면 끝입니다. 평균으로도 10,000번 대 13.4번, 약 750배 차이입니다. 삽입 시간은 55배 차이인데, AVL 이 매번 회전까지 하면서도 훨씬 빠릅니다. 사슬에 붙이는 것 자체가 O(n) 이기 때문입니다.
8.2 발상: 균형 인수
1962년에 두 소련 수학자(Adelson-Velsky 와 Landis, 그래서 AVL)가 제안한 아이디어는 간단합니다.
모든 노드에서 균형 인수 = 왼쪽 부분트리 높이 − 오른쪽 부분트리 높이 가 −1, 0, +1 중 하나여야 한다.
왼쪽과 오른쪽 높이 차이가 1을 넘지 않게 유지하면, 트리 전체 높이가 log₂ n 의 1.44배를 넘지 않는다는 것이 증명돼 있습니다. 노드 100만 개면 높이 최대 28, 보통은 20쯤입니다.
삽입할 때마다 이 조건이 깨졌는지 확인하고, 깨졌으면(±2가 되면) 회전(rotation) 으로 모양을 고칩니다. 그러려면 각 노드가 자기 높이를 알고 있어야 하므로, 노드 구조체에 height 를 추가합니다. examples/avl_tree.c:
typedef struct ANode {
int data;
int height; /* 이 노드를 루트로 하는 부분트리의 높이 */
struct ANode *left;
struct ANode *right;
} ANode;
int height(const ANode *n) {
return (n == NULL) ? -1 : n->height; /* 빈 트리 -1, 잎 0 */
}
void update_height(ANode *n) {
n->height = 1 + max_int(height(n->left), height(n->right));
}
/* 균형 인수: 왼쪽 높이 - 오른쪽 높이 */
int balance_factor(const ANode *n) {
return (n == NULL) ? 0 : height(n->left) - height(n->right);
}
2.5절의 tree_height 는 매번 트리를 전부 훑어서 O(n) 이었습니다. 여기서는 각 노드가 높이를 저장해 두고, 자식이 바뀔 때 update_height 로 갱신합니다. height(NULL) 이 −1인 것은 2.5절과 같은 이유입니다. 새 노드의 height 는 0(잎)으로 시작합니다.
8.3 회전: 규칙을 지키면서 모양 바꾸기
왼쪽이 너무 무거운 노드가 있다고 합시다. 왼쪽 자식을 위로 올리고 나를 그 오른쪽으로 내리면 높이가 줄어듭니다. 이것이 오른쪽 회전입니다.
오른쪽 회전: y x
/ \ / \
x C → A y
/ \ / \
A B B C
y가 무거운 노드,x가 그 왼쪽 자식입니다.x가 새 루트가 되고y는x의 오른쪽 자식이 됩니다.- 그럼 원래
x의 오른쪽 자식이던B는 갈 곳을 잃습니다.y의 왼쪽이 비었으니 거기로 보냅니다.
B 를 y 의 왼쪽에 붙여도 되는 이유를 확인합시다. B 는 원래 x 의 오른쪽에 있었으니 x 보다 크고, y 의 왼쪽 세계에 있었으니 y 보다 작습니다. 그러니 “x 와 y 사이”이고, 회전 후 y 의 왼쪽이 정확히 그 자리입니다. 중위 순회로 읽으면 회전 전후 모두 A x B y C 입니다. 정렬 순서가 그대로이니 BST 규칙이 유지됩니다.
코드로는 포인터 두 개를 옮기는 것이 전부입니다.
ANode *rotate_right(ANode *y) {
ANode *x = y->left;
ANode *B = x->right;
x->right = y;
y->left = B;
update_height(y); /* 아래(y)부터 갱신! */
update_height(x);
return x; /* 새 루트 */
}
이 함수도 “부분트리의 새 루트를 반환”합니다. 부른 쪽은 root = rotate_right(root) 처럼 받습니다.
높이 갱신 순서가 중요합니다. x 의 새 높이는 자식인 y 의 높이에 달려 있습니다. x 를 먼저 갱신하면 아직 옛날 값인 y 의 높이를 읽습니다. 회전으로 아래로 내려간 노드부터 갱신해야 합니다. 이 순서를 바꾸면 컴파일도 실행도 되지만 높이가 조금씩 틀어져서, 나중에 엉뚱한 곳에서 회전을 하거나 안 합니다. 11절에 넣어 둔 함정입니다.
왼쪽 회전은 좌우를 바꾼 대칭입니다.
/* 왼쪽 회전 (완전 대칭) */
ANode *rotate_left(ANode *x) {
ANode *y = x->right;
ANode *B = y->left;
y->left = x;
x->right = B;
update_height(x);
update_height(y);
return y;
}
8.4 네 가지 경우
균형이 깨지는 모양은 네 가지이고, 처방이 각각 다릅니다. “무거운 쪽의 무거운 쪽”으로 이름을 붙입니다.
| 경우 | 모양 | 처방 |
|---|---|---|
| LL | 왼쪽 자식의 왼쪽이 무겁다 | 오른쪽 회전 1번 |
| RR | 오른쪽 자식의 오른쪽이 무겁다 | 왼쪽 회전 1번 |
| LR | 왼쪽 자식의 오른쪽이 무겁다 | 왼쪽 자식을 왼쪽 회전 → 나를 오른쪽 회전 |
| RL | 오른쪽 자식의 왼쪽이 무겁다 | 오른쪽 자식을 오른쪽 회전 → 나를 왼쪽 회전 |
LL 과 RR 은 한 방향으로 쭉 기운 모양이라 한 번 돌리면 됩니다. LR 과 RL 은 꺾인 모양이라 한 번 돌리면 반대로 꺾일 뿐입니다. 먼저 자식을 돌려서 LL(또는 RR) 모양으로 편 다음 나를 돌립니다.
말로는 어려우니 삽입 과정을 한 단계씩 찍어 보겠습니다(avltrace.c, 각 노드 옆에 높이 h 와 균형 인수 bf 를 표시). 먼저 LL: 30, 20, 10 순서로 넣는 경우입니다.
=== LL: 30, 20, 10 ===
insert(30)
30 (h=0, bf=+0)
insert(20)
30 (h=1, bf=+1)
20 (h=0, bf=+0)
insert(10)
30 에서 bf=+2, 새 값이 왼쪽의 왼쪽 -> LL: rotate_right(30)
30 (h=0, bf=+0)
20 (h=1, bf=+0)
10 (h=0, bf=+0)
10 을 넣는 순간 30 의 균형 인수가 +2 가 됩니다(왼쪽 높이 1, 오른쪽 높이 −1). 새 값 10 이 30 의 왼쪽 자식(20)의 왼쪽에 들어갔으니 LL 입니다. rotate_right(30) 한 번으로 20 이 루트가 되고, 모든 노드의 균형 인수가 0 이 됐습니다.
이번엔 LR: 30, 10, 20 입니다.
=== LR: 30, 10, 20 ===
insert(30)
30 (h=0, bf=+0)
insert(10)
30 (h=1, bf=+1)
10 (h=0, bf=+0)
insert(20)
30 에서 bf=+2, 새 값이 왼쪽의 오른쪽 -> LR: rotate_left(10) 후 rotate_right(30)
(1차 회전 뒤)
30 (h=2, bf=+2)
20 (h=1, bf=+1)
10 (h=0, bf=+0)
30 (h=0, bf=+0)
20 (h=1, bf=+0)
10 (h=0, bf=+0)
20 은 30 의 왼쪽 자식(10)의 오른쪽에 들어갔습니다. 모양이 30 → 10 → 20 으로 꺾여 있습니다. 여기서 rotate_right(30) 만 하면 10 이 루트가 되고 30 이 오른쪽, 20 은 30 의 왼쪽으로 가서 이번엔 오른쪽으로 꺾입니다. 그래서 먼저 10 을 왼쪽 회전해서 30 → 20 → 10 의 LL 모양으로 편 뒤(“1차 회전 뒤” 그림), rotate_right(30) 으로 마무리합니다. 결과는 LL 때와 똑같은 트리입니다.
8.5 삽입에 붙이기
AVL 삽입 = BST 삽입 + 재귀가 풀려 돌아오는 길에 높이 갱신과 균형 검사. “부분트리의 새 루트를 반환” 패턴 덕분에 회전 결과를 그대로 돌려주면 됩니다.
/* AVL 삽입: BST 삽입 + 돌아오는 길에 균형 검사/회전 */
ANode *avl_insert(ANode *root, int data) {
/* 1. 평범한 BST 삽입 */
if (root == NULL) return node_create(data);
if (data < root->data) root->left = avl_insert(root->left, data);
else if (data > root->data) root->right = avl_insert(root->right, data);
else return root; /* 중복 무시 */
/* 2. 높이 갱신 */
update_height(root);
/* 3. 균형 검사 - 재귀가 풀리며 "삽입 경로의 조상들"이 차례로 검사된다 */
int bf = balance_factor(root);
if (bf > 1 && data < root->left->data) { /* LL */
rotation_count++;
return rotate_right(root);
}
if (bf < -1 && data > root->right->data) { /* RR */
rotation_count++;
return rotate_left(root);
}
if (bf > 1 && data > root->left->data) { /* LR */
rotation_count += 2;
root->left = rotate_left(root->left);
return rotate_right(root);
}
if (bf < -1 && data < root->right->data) { /* RL */
rotation_count += 2;
root->right = rotate_right(root->right);
return rotate_left(root);
}
return root; /* 균형 OK */
}
- 1단계는 5.2절의
bst_insert와 글자 하나 다르지 않습니다. - 2, 3단계는 재귀 호출 뒤에 있습니다. 즉 새 노드를 붙이고 나서 재귀가 풀려 올라오는 길에, 삽입 경로에 있던 조상들이 잎에 가까운 쪽부터 차례로 자기 높이를 갱신하고 균형을 검사합니다. 균형이 깨진 곳은 삽입 경로 위에만 있을 수 있으니 이것으로 충분합니다.
- 네 경우의 구분은
bf의 부호(어느 쪽이 무거운가)와, 새 값이 무거운 자식의 어느 쪽으로 갔는가(data < root->left->data등)로 합니다. rotation_count는 데모용으로 회전 횟수를 세는 전역 변수입니다.
이제 5.5절의 최악 입력을 다시 넣어 봅시다.
$ ./build/avl_tree
=== 실험: 1~10을 순서대로 삽입 (BST 최악의 입력!) ===
[순수 BST] 높이 = 9 (노드 10개가 한 줄로!)
10
9
8
7
6
5
4
3
2
1
[AVL] 높이 = 3 (회전 6번으로 균형 유지)
10
9
8
7
6
5
4
3
2
1
중위 순회는 둘 다 정렬: 1 2 3 4 5 6 7 8 9 10
=== 회전 4종 직접 확인 ===
LL (30,20,10 삽입) -> 루트 20 (항상 20이 루트가 된다!)
RR (10,20,30 삽입) -> 루트 20 (항상 20이 루트가 된다!)
LR (30,10,20 삽입) -> 루트 20 (항상 20이 루트가 된다!)
RL (10,30,20 삽입) -> 루트 20 (항상 20이 루트가 된다!)
높이 차이의 의미: 노드 100만 개일 때
- 사슬 BST : 탐색 최악 1,000,000번 이동
- AVL : 탐색 최악 약 20번 이동 (높이 <= 1.44 log n)
AVL 트리의 회전
같은 1~10 인데 순수 BST 는 높이 9 의 사슬, AVL 은 회전 6번으로 높이 3 입니다. 눕힌 그림을 바로 세우면 이렇습니다.
4
/ \
2 8
/ \ / \
1 3 6 9
/ \ \
5 7 10
10, 20, 30 세 값은 어떤 순서로 넣어도 20 이 루트가 됩니다. 네 경우의 처방이 모두 같은 균형 트리에 도달한다는 뜻입니다.
삭제는? AVL 삭제는 “BST 삭제 + 돌아오는 길에 회전”으로 삽입과 원리가 같지만, 경우가 더 많고 회전이 여러 번 연쇄될 수 있어 이번 주 범위를 넘습니다. 도전 과제로 남겨 두었습니다. 참고로 리눅스 커널과 대부분의 표준 라이브러리는 AVL 의 사촌인 레드-블랙 트리를 씁니다. 균형 조건이 조금 느슨해서 회전이 덜 일어나는데, “회전으로 균형을 잡는다”는 원리는 같습니다. AVL 을 이해했다면 그쪽도 금방 읽힙니다.
9. 힙: 배열에 사는 트리
9.1 느슨한 규칙이 주는 것
11주차 우선순위 큐를 떠올려 보세요. “가장 급한 것 하나”를 꺼내는 것이 목적이었는데, 정렬된 리스트에 넣느라 삽입이 O(n) 이었습니다. BST 로 만들면 삽입도 최솟값 찾기도 O(log n) 이지만, 사실 “최솟값 하나”만 필요한데 전체 정렬 순서를 유지하는 BST 는 과합니다.
힙(heap) 은 규칙을 딱 필요한 만큼만 남긴 트리입니다.
부모 ≤ 자식 (최소 힙). 형제끼리는 아무 관계 없어도 된다.
이 규칙만 있으면 최솟값이 항상 루트입니다. 부모가 자식보다 작으니 위로 갈수록 작아지고, 루트가 가장 작습니다. 왼쪽 자식이 오른쪽 자식보다 클 수도 있고, 중위 순회를 해도 정렬돼 나오지 않습니다. 대신 규칙이 느슨한 덕분에 트리를 항상 완전 이진 트리(위에서 아래로, 왼쪽에서 오른쪽으로 빈틈없이 채운 모양)로 유지할 수 있습니다.
이름이 같은 다른 것: 7주차의 메모리 영역 “힙”과 자료구조 “힙”은 이름만 같고 관계가 없습니다. 메모리 힙은 “쌓여 있는 더미”라는 일반 명사에서, 자료구조 힙은 1964년 힙 정렬 논문에서 왔습니다. 이 절에서 힙은 자료구조입니다.
9.2 포인터 없이 배열로
완전 이진 트리의 진짜 매력은 포인터가 필요 없다는 것입니다. 빈틈이 없으니 위에서부터 번호를 붙이면 배열에 그대로 담기고, 부모와 자식이 인덱스 계산만으로 찾아집니다.
1 배열: [1, 3, 9, 7, 5]
/ \ 0 1 2 3 4
3 9
/ \ 부모 = (i - 1) / 2
7 5 왼쪽 자식 = 2*i + 1
오른쪽 = 2*i + 2
확인해 봅시다. 3 은 인덱스 1이고, 자식은 2×1+1 = 3 번(7)과 2×1+2 = 4 번(5)입니다. 5 의 부모는 (4−1)/2 = 1 번, 즉 3 입니다. 정수 나눗셈이 버림을 하는 것(3주차)을 이용한 공식입니다.
TNode 의 24바이트 중 16바이트가 포인터였습니다. 힙은 그 16바이트를 전부 없애고 값 4바이트만 씁니다. 그리고 배열이라 10주차에서 배운 대로 캐시에도 훨씬 유리합니다.
9.3 삽입: 맨 뒤에 넣고 위로 올리기
examples/heap_basic.c 의 최소 힙입니다. 10주차의 동적 배열(realloc 으로 두 배씩)을 그대로 씁니다.
typedef struct {
int *data;
size_t size;
size_t capacity;
} MinHeap;
삽입은 두 단계입니다. 맨 뒤(배열 끝)에 넣고, 부모보다 작으면 부모와 자리를 바꾸며 위로 올라갑니다(sift-up).
/* 위로 올리기: 부모보다 작으면 교환하며 상승 */
static void sift_up(MinHeap *h, size_t i) {
while (i > 0) {
size_t parent = (i - 1) / 2;
if (h->data[i] >= h->data[parent]) break; /* 자리 찾음 */
swap(&h->data[i], &h->data[parent]);
i = parent;
}
}
int heap_push(MinHeap *h, int value) {
if (h->size == h->capacity) {
size_t cap = (h->capacity == 0) ? 8 : h->capacity * 2;
int *tmp = realloc(h->data, cap * sizeof(int));
if (tmp == NULL) return 0;
h->data = tmp;
h->capacity = cap;
}
h->data[h->size] = value; /* 1. 맨 뒤에 추가 */
sift_up(h, h->size); /* 2. 제자리로 상승 */
h->size++;
return 1;
}
while (i > 0): 루트(인덱스 0)에 도달하면 더 올라갈 곳이 없습니다.if (h->data[i] >= h->data[parent]) break;: 부모가 나보다 작거나 같으면 규칙이 지켜진 것이니 멈춥니다.- 맨 뒤에 넣으면 완전 이진 트리 모양이 유지되고, 위로 올라가는 동안 다른 가지는 건드리지 않으니 규칙도 유지됩니다. 올라가는 횟수는 최대 트리 높이, 즉 O(log n) 입니다.
7, 3, 9, 1, 5 를 차례로 넣는 과정을 예제가 그대로 찍어 줍니다.
$ ./build/heap_basic
=== 삽입: 7, 3, 9, 1, 5 ===
push(7):
배열: [7]
레벨: 7
push(3):
배열: [3 7]
레벨: 3
레벨: 7
push(9):
배열: [3 7 9]
레벨: 3
레벨: 7 9
push(1):
배열: [1 3 9 7]
레벨: 1
레벨: 3 9
레벨: 7
push(5):
배열: [1 3 9 7 5]
레벨: 1
레벨: 3 9
레벨: 7 5
push(1) 을 따라가 봅시다. 배열 [3 7 9] 의 맨 뒤(인덱스 3)에 1 을 넣습니다. 부모는 (3−1)/2 = 1 번의 7. 1 < 7 이니 교환 → [3 1 9 7]. 이제 인덱스 1, 부모는 0 번의 3. 1 < 3 이니 교환 → [1 3 9 7]. 인덱스 0 에 도착해 끝. 두 번 교환으로 1 이 루트까지 올라갔습니다.
마지막 배열 [1 3 9 7 5] 를 보세요. 정렬돼 있지 않습니다(9 가 5 앞에 있습니다). 하지만 트리로 그리면 모든 부모가 자식보다 작습니다. 힙은 완전 정렬이 아니라 “부모 ≤ 자식”만 보장합니다. 이 점을 프로젝트 3에서 다시 확인합니다.
9.4 추출: 루트를 빼고 아래로 내리기
최솟값은 루트에 있으니 꺼내는 것은 쉽습니다. 문제는 빈 루트 자리를 메우는 것입니다. 트리 모양을 유지하려면 없어져야 할 것은 배열의 맨 뒤 원소입니다. 그래서 맨 뒤 원소를 루트로 올리고, 그 값이 자식보다 크면 작은 쪽 자식과 바꾸며 내려갑니다(sift-down).
/* 아래로 내리기: 두 자식 중 작은 쪽과 교환하며 하강 */
static void sift_down(MinHeap *h, size_t i) {
while (1) {
size_t smallest = i;
size_t left = 2 * i + 1;
size_t right = 2 * i + 2;
if (left < h->size && h->data[left] < h->data[smallest]) smallest = left;
if (right < h->size && h->data[right] < h->data[smallest]) smallest = right;
if (smallest == i) break; /* 두 자식 모두 나보다 크다 */
swap(&h->data[i], &h->data[smallest]);
i = smallest;
}
}
int heap_pop(MinHeap *h, int *out) {
if (h->size == 0) return 0;
if (out != NULL) *out = h->data[0]; /* 최솟값은 항상 루트 */
h->size--;
h->data[0] = h->data[h->size]; /* 맨 뒤를 루트로 */
sift_down(h, 0); /* 제자리로 하강 */
return 1;
}
left < h->size검사는 “자식이 존재하는가”입니다. 배열 끝을 넘어가는 인덱스는 자식이 없는 것입니다.- 작은 쪽 자식과 바꿔야 합니다. 큰 쪽과 바꾸면 그 큰 자식이 위로 올라와 남은 작은 자식보다 커지니 규칙이 깨집니다. 11절의 함정 목록에 있습니다.
smallest == i이면 두 자식 모두 나보다 크거나 같으니 제자리입니다.
[1 3 9 7 5] 에서 첫 번째 pop 이 일어나는 과정입니다.
꺼낼 값: data[0] = 1
맨 뒤(5)를 루트로: [5 3 9 7] (size 는 4 로)
sift_down(0): 자식은 data[1]=3, data[2]=9. 작은 쪽은 3. 5 > 3 이니 교환
[3 5 9 7]
sift_down(1): 자식은 data[3]=7 뿐. 5 < 7 이니 제자리. 끝
루트에 올라온 5 가 한 층 내려가 제자리를 찾았습니다. 다음 최솟값 3 이 루트에 있습니다. 배열 뒤쪽의 9 와 7 은 건드리지 않았습니다. 내려가는 횟수 역시 최대 트리 높이라 O(log n) 입니다.
heap_pop 을 반복하면 최솟값부터 차례로 나옵니다.
=== 추출: 항상 최솟값부터 나온다 ===
pop() = 1
pop() = 3
pop() = 5
pop() = 7
pop() = 9
정렬한 적 없는데 정렬 순서로! (이것이 다음 예제 힙 정렬의 원리)
9.5 실험: 부모 공식을 틀리면
부모 인덱스를 (i − 1) / 2 대신 i / 2 로 쓰는 실수가 흔합니다. 1부터 번호를 매기는 교과서의 공식을 0부터 매기는 C 배열에 그대로 옮기면 이렇게 됩니다. 인덱스 1과 2의 부모는 둘 다 0이어야 하는데, i / 2 로는 2의 부모가 1이 됩니다. 어떻게 잘못되는지 확인해 봅시다(heapidx3.c).
$ ./heapidx3
부모 = (i-1)/2 (맞음): [1 2 5 4 6 9 7]
pop 순서: 1 2 4 5 6 7 9
부모 = i/2 (틀림) : [1 2 6 4 9 7 5] <- data[6]=5 의 진짜 부모 data[2]=6 가 더 크다!
pop 순서: 1 2 4 5 6 7 9
1, 2, 9, 4, 6, 7, 5 를 넣었을 때, 틀린 공식은 5 를 엉뚱한 부모(인덱스 3)와 비교하고 멈춰 버려서 부모 6 아래에 자식 5 가 놓인 힙이 됩니다. 규칙이 깨졌습니다. 그런데 pop 순서는 우연히 맞습니다. 이런 버그가 무서운 이유입니다. 대부분의 입력에서 결과가 맞고, 어떤 입력에서만 틀린 답을 내는데, 그게 언제인지 알 수 없습니다. 힙의 인덱스 공식 세 개는 외우세요. 부모 (i−1)/2, 왼쪽 2i+1, 오른쪽 2i+2.
9.6 힙 정렬
“pop 을 반복하면 정렬 순서로 나온다”를 그대로 정렬 알고리즘으로 만든 것이 힙 정렬입니다. examples/heap_sort.c 는 배열 하나 안에서 자리만 바꿔 정렬합니다.
- 배열을 최대 힙(부모 ≥ 자식)으로 만든다. heapify 라고 합니다.
- 루트(최댓값)를 배열 맨 뒤와 바꾸고, 힙의 크기를 하나 줄인다. 맨 뒤는 이제 “정렬 완료 영역”이다.
- 새 루트를
sift_down으로 제자리에 보낸다. - 힙 크기가 1이 될 때까지 2~3 을 반복한다.
void heap_sort(int arr[], int n) {
/* 1단계: 배열을 최대 힙으로 (heapify)
* 마지막 내부 노드부터 거꾸로 sift-down.
* 잎들은 이미 힙이므로 절반은 공짜! -> 전체 O(n) */
for (int i = n / 2 - 1; i >= 0; i--) {
sift_down(arr, n, i);
}
/* 2단계: 루트(최댓값)를 뒤로 보내며 줄이기 */
for (int size = n - 1; size > 0; size--) {
swap(&arr[0], &arr[size]); /* 최댓값을 정렬 영역으로 */
sift_down(arr, size, 0); /* 줄어든 힙을 복구 */
}
}
heapify 가 n / 2 − 1 부터 시작하는 이유: 인덱스 n/2 이후는 전부 잎이라(자식 인덱스 2i+1 ≥ n) 이미 크기 1짜리 힙입니다. 자식이 있는 마지막 노드부터 거꾸로 sift_down 하면 아래쪽부터 힙이 완성됩니다.
$ ./build/heap_sort
=== 힙 정렬 ===
원본: [5 9 1 7 3 8 2]
--- 1단계: heapify (뒤쪽 내부 노드부터 sift-down) ---
힙 완성: [9 7 8 5 3 1 2]
(arr[0]=9가 최댓값)
--- 2단계: 최댓값을 하나씩 뒤로 (| 오른쪽은 정렬 완료) ---
[8 7 2 5 3 1 | 9]
[7 5 2 1 3 | 8 9]
[5 3 2 1 | 7 8 9]
[3 1 2 | 5 7 8 9]
[2 1 | 3 5 7 8 9]
[1 | 2 3 5 7 8 9]
결과: [1 2 3 5 7 8 9]
| 오른쪽이 정렬이 끝난 영역입니다. 한 번 돌 때마다 최댓값 하나가 오른쪽으로 넘어가고 힙이 하나씩 줄어듭니다. 최대 힙을 쓰는 이유는 가장 큰 것을 맨 뒤로 보내야 오름차순이 되기 때문입니다.
힙 정렬의 장점은 최악의 경우에도 O(n log n) 이고 추가 메모리가 필요 없다는 것입니다. 15주차 정렬 대전에서 퀵 정렬, 병합 정렬과 비교하게 됩니다.
9.7 지난주의 약속: O(n) 에서 O(log n) 으로
11주차 우선순위 큐의 삽입은 정렬된 자리를 찾느라 O(n) 이었습니다. 그때 “다음 주 힙으로 O(log n) 을 만든다”고 약속했습니다. examples/heap_pq_compare.c 는 같은 우선순위 값 20,000개를 두 방식에 똑같이 넣고 시간을 잽니다.
$ ./build/heap_pq_compare
우선순위 큐 대결: 20000개 삽입 + 전체 추출
(우선순위는 유사 난수, 두 방식에 동일한 순서로 입력)
삽입 20000개 추출 20000개
정렬 리스트 : 457.45 ms 0.27 ms
최소 힙 : 0.56 ms 2.44 ms
삽입에서 힙이 약 813배 빠름!
검증: 우선순위 순서 OK / 합계 일치 OK
이유:
- 정렬 리스트 삽입: 자리 찾기 평균 n/2번 이동 -> 전체 O(n^2)
- 힙 삽입: 트리 높이만큼만(log n) 이동 -> 전체 O(n log n)
- 20000개면 20000^2 = 4e+08 vs 20000 x log2(20000) ≈ 3e+05
힙 vs 정렬 배열
삽입에서 800배입니다. 반대로 추출은 정렬 리스트가 빠릅니다. 이미 정렬돼 있으니 맨 앞을 떼기만 하면 되니까요(O(1)). 힙은 매번 sift_down 을 해야 합니다(O(log n)). 그래도 합치면 460ms 대 3ms 입니다. 어떤 자료구조도 모든 연산에서 이기지는 않습니다. 자주 하는 연산이 무엇인지에 따라 고르는 것이고, 우선순위 큐는 삽입과 추출이 번갈아 일어나니 힙이 맞는 도구입니다.
수치는 실행할 때마다 조금씩 다릅니다(이 글의 수치와 그림의 수치가 다른 이유입니다). 몇 배인지가 아니라 O(n²) 과 O(n log n) 의 차이를 보세요. n 이 열 배가 되면 이 차이는 100배 더 벌어집니다.
10. 실습 프로젝트
세 프로젝트는 이번 주 내용을 실제 문제에 붙여 봅니다. 셋 다 make 로 이미 빌드돼 있습니다. 코드는 길지만 새로운 문법은 거의 없습니다. 이번 주의 순회 세 가지와 힙이 각각 어디에 쓰이는지에 집중하세요.
프로젝트 1: 파일 시스템 트리 (file_tree.c)
들어가며에서 본 폴더 구조를 직접 만듭니다. 그런데 바로 문제가 하나 생깁니다. 폴더는 자식이 몇 개든 가질 수 있습니다. left 와 right 두 개뿐인 이진 트리로는 안 됩니다. 자식 수만큼 포인터 배열을 두면 될까요? 자식이 몇 개일지 미리 모르니 매번 realloc 해야 하고, 노드마다 배열이 하나씩 붙어 무겁습니다.
고전적인 해법이 있습니다. “첫째 자식과 다음 형제(first-child, next-sibling)” 표현입니다.
typedef struct FNode {
char name[MAX_NAME];
FType type;
long size; /* 파일 크기 (디렉토리는 0) */
struct FNode *child; /* 첫째 자식 */
struct FNode *sibling; /* 다음 형제 */
} FNode;
포인터가 딱 두 개인데 자식이 몇 명이든 표현합니다. child 는 첫째 자식만 가리키고, 나머지 자식들은 첫째부터 sibling 으로 이어진 연결 리스트입니다.
일반 트리 모양 first-child / next-sibling 으로 저장한 모양
home home
/ | \ │ child
user docs etc user ─sibling→ docs ─sibling→ etc
/ \ │ child
a.c b.c a.c ─sibling→ b.c
오른쪽 그림을 45도 돌려 보면 child 를 왼쪽, sibling 을 오른쪽으로 한 이진 트리입니다. 어떤 트리든 이진 트리로 바꿀 수 있다는, 자료구조 교과서의 오래된 정리가 이것입니다.
어떤 폴더의 자식들을 훑는 코드는 리스트 순회 그대로입니다.
/* 디렉토리 안에서 이름 찾기: 자식들을 sibling으로 순회 */
FNode *dir_find_child(FNode *dir, const char *name) {
for (FNode *c = dir->child; c != NULL; c = c->sibling) {
if (strcmp(c->name, name) == 0) return c;
}
return NULL;
}
home/user/src 같은 경로를 따라 내려가는 것은 strtok 으로 / 마다 잘라서 한 단계씩 dir_find_child 하는 것입니다. strtok 은 문자열을 구분자에서 잘라 조각을 하나씩 돌려주는 표준 함수로, 원본 문자열 안에 \0 을 써넣어 자르기 때문에 복사본(copy)에 대고 씁니다.
for (char *tok = strtok(copy, "/"); tok != NULL; tok = strtok(NULL, "/")) {
if (cur->type != FT_DIR) return NULL; /* 파일 아래로는 못 간다 */
cur = dir_find_child(cur, tok);
if (cur == NULL) return NULL;
}
순회 세 가지가 각자 일을 맡는다
이 프로그램의 명령 세 개가 이번 주의 순회 세 가지와 정확히 대응합니다.
tree = 전위 순회. 나를 먼저 출력하고 자식들을 출력합니다. 리눅스의 tree 명령이 하는 일 그대로입니다.
/* tree 출력: 전위 순회 (나 먼저, 자식들 다음) */
void tree_show(const FNode *node, int depth) {
for (int i = 0; i < depth; i++) printf(" ");
if (node->type == FT_DIR) {
printf("%s/\n", node->name);
} else {
printf("%s (%ld바이트)\n", node->name, node->size);
}
for (const FNode *c = node->child; c != NULL; c = c->sibling) {
tree_show(c, depth + 1);
}
}
du = 후위 순회. 폴더의 크기는 자식들의 크기를 먼저 다 합쳐야 알 수 있습니다. 리눅스 du 명령의 원리입니다.
/* du: 후위 순회로 크기 합산 (자식들 합을 구한 뒤 내 것 더하기) */
long tree_du(const FNode *node) {
long total = node->size;
for (const FNode *c = node->child; c != NULL; c = c->sibling) {
total += tree_du(c);
}
return total;
}
find = 전위 순회 + 백트래킹. 5주차 미로 탐색에서 본 백트래킹입니다. 내려가면서 경로 문자열 끝에 내 이름을 붙이고, 자식들을 다 본 뒤 돌아올 때 내 이름을 지웁니다.
/* find: 전위 순회로 이름 검색, 경로를 조립해 출력 */
void tree_find(const FNode *node, const char *name, char *path, size_t pathlen) {
size_t old = strlen(path);
snprintf(path + old, MAX_PATH - old, "%s%s",
(old == 0) ? "" : "/", node->name);
if (strcmp(node->name, name) == 0) {
printf(" %s%s\n", path, node->type == FT_DIR ? "/" : "");
}
for (const FNode *c = node->child; c != NULL; c = c->sibling) {
tree_find(c, name, path, pathlen);
}
path[old] = '\0'; /* 백트래킹: 내 이름 지우기 */
}
old 에 들어올 때의 길이를 기억해 두고, 나갈 때 path[old] = '\0' 으로 그 뒤를 잘라 냅니다. 4주차에서 배운 “\0 이 문자열의 끝”을 이용한 것입니다. 이렇게 하면 경로 버퍼 하나를 온 트리가 돌려 씁니다.
삭제 rm 은 부모의 자식 리스트에서 나를 빼고(10주차 리스트 삭제), 내 부분트리를 후위 순회로 해제합니다. 한 가지 요령이 있습니다.
c->sibling = NULL; /* 형제 사슬을 끊고 나만 해제 */
tree_free(c);
tree_free 는 child 와 sibling 을 둘 다 따라가며 지웁니다. 형제 사슬을 끊지 않고 부르면 내 뒤의 형제들까지 전부 지워 버립니다. 이 한 줄이 없으면 rm home/user/src 가 옆에 있던 docs 까지 지웁니다.
실행
대화형 프로그램이라 명령을 직접 칩니다. 샘플 트리가 들어 있습니다.
$ ./build/file_tree
파일 시스템 트리 (help: 도움말)
샘플 트리가 준비되어 있습니다. tree를 입력해 보세요.
=====================================
> tree
/
home/
user/
hello.c (320바이트)
memo.txt (120바이트)
src/
main.c (1500바이트)
util.c (800바이트)
etc/
config.ini (250바이트)
> du home/user
home/user 총 크기: 2740바이트
> du /
/ 총 크기: 2990바이트
> find main.c
'main.c' 검색 결과:
home/user/src/main.c
> mkdir home/docs
생성됨: home/docs/
> touch home/docs/a.txt 100
생성됨: home/docs/a.txt
> rm home/user/src
삭제됨: home/user/src
> du home
home 총 크기: 540바이트
> q
종료 (모든 노드 해제 - 누수 0)
du home/user 의 2740 은 320 + 120 + 1500 + 800 입니다. src 를 지운 뒤 home 이 540 (320 + 120 + 100) 으로 준 것을 확인하세요. 잘못된 명령은 이렇게 거절합니다.
> mkdir home/user
실패 (경로/중복 확인): home/user
> touch nowhere/a.txt 5
실패 (경로/중복 확인): nowhere/a.txt
> rm home/nope
실패 (경로 확인): home/nope
디렉터리 트리
확장 아이디어: cd 와 pwd(현재 위치 개념 추가), mv(부분트리를 떼어 다른 곳에 붙이기), 9주차와 연계해 트리를 파일에 저장하고 복원하기(전위 순회로 저장하면 복원이 쉽습니다).
프로젝트 2: 표현식 파서와 AST (expr_parser.c)
11주차 후위 표기법 계산기는 2 3 4 + * 처럼 사람이 후위 표기로 써 줘야 했습니다. 이번엔 2 * (3 + 4) 를 그대로 받아서 트리로 만듭니다. 이 트리를 추상 구문 트리(AST, Abstract Syntax Tree) 라고 하고, 1주차 7절에서 본 컴파일러가 여러분의 C 코드를 읽어 만드는 것이 바로 이것입니다.
"2 * (3 + 4)" → *
/ \
2 +
/ \
3 4
연산자가 안쪽 노드, 숫자가 잎입니다. 괄호는 사라졌습니다. 괄호가 하던 일(먼저 계산할 것 정하기)을 트리의 모양이 대신하기 때문입니다. + 가 * 아래에 있으니 먼저 계산됩니다.
문법 규칙 하나가 함수 하나
문자열을 트리로 바꾸는 것을 파싱(parsing) 이라고 합니다. 여기서는 가장 직관적인 기법인 재귀 하강(recursive descent) 을 씁니다. 수식의 문법을 세 규칙으로 적습니다.
expr = term (('+'|'-') term)* ← 식 = 항을 +,- 로 이은 것
term = factor (('*'|'/') factor)* ← 항 = 인수를 *,/ 로 이은 것
factor = 숫자 | '(' expr ')' | '-' factor ← 인수 = 숫자, 괄호 식, 또는 -인수
( ... )* 는 “0번 이상 반복”입니다. 그리고 규칙 하나를 함수 하나로 옮깁니다.
/* expr = term (('+'|'-') term)* */
Ast *parse_expr(Parser *p) {
Ast *left = parse_term(p);
while (!p->error) {
char c = peek(p);
if (c != '+' && c != '-') break;
advance(p);
Ast *right = parse_term(p);
left = ast_binop(c, left, right); /* 왼쪽 결합으로 쌓인다 */
}
return left;
}
peek은 공백을 건너뛰고 다음 글자를 보기만 하고,advance는 한 글자 소비합니다.term하나를 읽고,+나-가 보이는 동안 다음term을 읽어 지금까지의 트리를 왼쪽 자식으로 하는 새 노드를 만듭니다. 그래서2 - 3 - 4는(2 - 3) - 4가 됩니다(왼쪽 결합). 오른쪽 결합이면2 - (3 - 4) = 3으로 틀린 답이 나옵니다.
parse_term 은 + - 가 * / 로 바뀐 것뿐입니다. parse_factor 가 재귀의 바닥입니다.
/* factor = 숫자 | '(' expr ')' | '-' factor */
Ast *parse_factor(Parser *p) {
char c = peek(p);
if (c == '-') { /* 단항 마이너스 */
advance(p);
return ast_neg(parse_factor(p));
}
if (c == '(') {
advance(p);
Ast *inner = parse_expr(p);
if (peek(p) != ')') {
p->error = 1; /* 닫는 괄호 없음 */
return inner;
}
advance(p);
return inner;
}
if (isdigit((unsigned char)c)) {
char *end;
double v = strtod(p->src + p->pos, &end);
p->pos = (size_t)(end - p->src);
return ast_num(v);
}
p->error = 1; /* 예상 밖의 문자 */
return ast_num(0);
}
괄호를 만나면 parse_expr 을 다시 부릅니다. expr 이 term 을 부르고, term 이 factor 를 부르고, factor 가 괄호 안에서 다시 expr 을 부르는 서로 재귀(mutual recursion) 입니다. 그래서 세 함수는 파일 위쪽에 전방 선언돼 있습니다(5주차 프로토타입).
strtod 는 문자열 앞부분을 실수로 바꿔 주는 표준 함수(string to double)입니다. 숫자를 읽고 두 번째 인자 end 에 “숫자가 끝난 위치”를 넣어 주므로, 거기까지 pos 를 옮깁니다. 1e3 같은 지수 표기도 읽어서 1e3 + 1 은 1001 이 됩니다.
호출 순서 따라가기
“+ 가 * 아래에 오는” 이유는 함수 호출 깊이에 있습니다. 2 * (3 + 4) 를 파싱하면서 함수가 불리고 돌아오는 순서를 찍어 봤습니다(parsetrace.c, 트리 대신 값을 바로 계산하는 축소판).
expr 시작 (남은 입력: "2 * (3 + 4)")
term 시작 (남은 입력: "2 * (3 + 4)")
factor 시작 (남은 입력: "2 * (3 + 4)")
숫자 2 읽음
factor 끝 -> 2
'*' 읽음
factor 시작 (남은 입력: " (3 + 4)")
expr 시작 (남은 입력: "3 + 4)") ← 괄호를 만나 expr 을 다시 부른다
term 시작 (남은 입력: "3 + 4)")
factor 시작 (남은 입력: "3 + 4)")
숫자 3 읽음
factor 끝 -> 3
term 끝 -> 3
'+' 읽음
term 시작 (남은 입력: " 4)")
factor 시작 (남은 입력: " 4)")
숫자 4 읽음
factor 끝 -> 4
term 끝 -> 4
expr 끝 -> 7 ← 괄호 안이 먼저 완성된다
factor 끝 -> 7
term 끝 -> 14
expr 끝 -> 14
결과: 14
* 를 처리하는 term 이 오른쪽 인수를 얻으려고 factor 를 불렀고, 그 factor 가 괄호 때문에 expr 을 통째로 다시 돌린 뒤에야 7을 돌려받았습니다. 곱셈의 오른쪽 자식이 덧셈 트리 전체가 되는 순간입니다. 우선순위를 처리하는 코드가 어디에도 따로 없는데, 규칙을 expr → term → factor 순서로 층을 나눠 놓은 것만으로 낮은 우선순위가 트리 위층에 오게 됩니다.
AST 가 생기면 나머지는 전부 순회
/* 계산 = 후위 순회 (자식 값을 구한 뒤 나를 계산) */
double eval(const Ast *node, int *ok) {
switch (node->type) {
case AST_NUM:
return node->value;
case AST_NEG:
return -eval(node->left, ok);
case AST_BINOP: {
double a = eval(node->left, ok);
double b = eval(node->right, ok);
switch (node->op) {
case '+': return a + b;
case '-': return a - b;
case '*': return a * b;
case '/':
if (b == 0.0) { *ok = 0; return 0; }
return a / b;
}
}
}
*ok = 0;
return 0;
}
- 계산 = 후위 순회. 두 자식의 값을 먼저 구하고 나를 계산합니다.
du와 같은 구조입니다. - 괄호 친 수식 출력 = 중위 순회. 왼쪽 → 연산자 → 오른쪽 순서로 찍으면서 괄호로 감쌉니다.
- 후위 표기 출력 = 후위 순회. 왼쪽, 오른쪽, 연산자 순서로 찍으면 11주차 계산기가 받던 입력이 그대로 나옵니다.
$ ./build/expr_parser "1 + 2 * 3 - 4 / 2"
표현식 파서와 AST
========================================
수식: 1 + 2 * 3 - 4 / 2
AST (옆으로 눕힌 트리):
2
/
4
-
3
*
2
+
1
중위(괄호 명시): ((1 + (2 * 3)) - (4 / 2))
후위(지난주 형식): 1 2 3 * + 4 2 / -
결과: 5
수식 파서
중위 출력을 보면 파서가 우선순위를 어떻게 이해했는지 그대로 드러납니다. 2 * 3 과 4 / 2 가 먼저 묶였고, 뺄셈이 맨 바깥입니다. 인자 없이 실행하면 단항 마이너스, 0 나눗셈, 문법 오류까지 여섯 가지 데모가 돌아갑니다.
$ ./build/expr_parser "2 * -(1 + 2)"
...
중위(괄호 명시): (2 * (-(1 + 2)))
후위(지난주 형식): 2 1 2 + ~ *
결과: -6
$ ./build/expr_parser "10 / (5 - 5)"
...
결과: 계산 오류 (0 나눗셈?)
$ ./build/expr_parser "2 + * 3"
...
-> 문법 오류!
$ ./build/expr_parser "(1 + 2"
...
-> 문법 오류!
2 + * 3 은 + 뒤에서 term → factor 가 * 를 만나 “숫자도 괄호도 마이너스도 아니다”라며 오류를 냅니다. 11주차 계산기는 사람이 후위 표기로 바꿔 준 입력을 받았으니 이런 검사를 할 기회가 없었는데, 파서는 문법에 어긋나는 바로 그 자리에서 멈춥니다. 컴파일러가 error: expected ';' before ... 처럼 정확한 위치를 짚어 주는 것이 바로 이 구조 덕분입니다.
확장 아이디어: 변수와 대입(x = 3, 그러려면 이름을 저장할 곳이 필요합니다. 13주차 해시 테이블이 딱입니다), 거듭제곱 ^(오른쪽 결합입니다. 2 ^ 3 ^ 2 = 2 ^ 9. 재귀 하강에서 오른쪽 결합을 어떻게 만들지 생각해 보세요), 오류 위치(몇 번째 글자인지) 출력.
프로젝트 3: 우선순위 작업 관리자 (task_manager.c)
11주차 작업 스케줄러를 힙으로 다시 만듭니다. 9절의 힙은 int 만 담았는데, 이번엔 구조체를 담습니다.
typedef struct {
char name[MAX_NAME];
int priority; /* 1=긴급 ... 9=한가할 때 */
long seq; /* 등록 순번 (동순위 tie-break) */
} Task;
/* Task 비교: 우선순위 먼저, 같으면 등록 순서 (작을수록 먼저) */
int task_less(const Task *a, const Task *b) {
if (a->priority != b->priority) return a->priority < b->priority;
return a->seq < b->seq;
}
힙 코드에서 h->data[i] < h->data[parent] 였던 곳이 전부 task_less(&h->data[i], &h->data[parent]) 로 바뀌었을 뿐, sift-up 과 sift-down 은 9절과 같습니다. “무엇이 더 작은가”만 함수로 빼면 어떤 타입이든 힙에 담을 수 있습니다. 10주차의 제네릭 정렬에서 비교 함수를 넘겼던 것과 같은 발상입니다.
seq 필드가 있는 이유
11주차 정렬 리스트 우선순위 큐에서는 같은 우선순위끼리 먼저 넣은 것이 먼저 나왔습니다(안정성). 힙은 그렇지 않습니다. 같은 우선순위 두 개가 sift-up, sift-down 을 거치면서 순서가 뒤바뀔 수 있습니다. 그래서 등록 순번 seq 를 두고, 우선순위가 같으면 seq 로 비교합니다. 비교 기준을 하나 더 넣어 안정성을 되찾은 것입니다.
힙 배열을 그대로 출력하면 안 되는 이유
작업 목록(p)을 보여 줄 때 힙 배열을 순서대로 찍으면 9.3절에서 본 대로 뒤죽박죽입니다. 예제는 힙을 복사한 뒤 복사본에서 pop 을 반복해서 실제 실행 순서를 보여 줍니다.
$ ./build/task_manager
우선순위 작업 관리자 - 힙 기반 (h: 도움말)
=====================================
> a 2 코드리뷰
추가됨: [P2] 코드리뷰 (대기 1개)
> a 1 서버복구
추가됨: [P1] 서버복구 (대기 2개)
> a 3 백업
추가됨: [P3] 백업 (대기 3개)
> a 1 장애보고
추가됨: [P1] 장애보고 (대기 4개)
> p
실행 예정 순서:
1. [P1] 서버복구
2. [P1] 장애보고
3. [P2] 코드리뷰
4. [P3] 백업
(내부 힙 배열: 서버복구(P1) 장애보고(P1) 백업(P3) 코드리뷰(P2) <- 이 순서 자체는 뒤죽박죽!)
> n
>>> 실행: [P1] 서버복구 (남은 작업 3개)
> n
>>> 실행: [P1] 장애보고 (남은 작업 2개)
> q
종료 (힙 해제 - 누수 0)
같은 P1 인 서버복구와 장애보고는 등록 순서대로 나왔고, 내부 배열에서는 P3 백업이 P2 코드리뷰보다 앞에 있습니다. 힙은 루트만 최솟값을 보장할 뿐, 배열 순서는 실행 순서가 아닙니다.
확장 아이디어: 우선순위 변경(힙 안의 원소를 찾아 값을 바꾸고 sift-up 또는 sift-down), 마감 시각 필드와 그것을 반영한 비교 함수, 9주차 연계로 작업 목록 저장과 복원.
세 프로젝트를 한 번에 검사하기
Makefile 에 memcheck 타깃이 있습니다. 5주차에서 배운 대로 타깃 이름을 주면 그 규칙만 실행됩니다. 대화형 프로그램 둘은 11주차에서 쓴 방법대로 printf 로 입력을 파이프에 넣어 검사합니다.
$ make memcheck
=== binary_tree_basic 누수 검사 ===
...
in use at exit: 0 bytes in 0 blocks
All heap blocks were freed -- no leaks are possible
ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
=== bst_delete 누수 검사 ===
...
=== file_tree 누수 검사 (파이프 입력) ===
...
All heap blocks were freed -- no leaks are possible
ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
=== task_manager 누수 검사 (파이프 입력) ===
...
All heap blocks were freed -- no leaks are possible
ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
여섯 프로그램 모두 All heap blocks were freed 와 0 errors 입니다. 트리를 만드는 프로그램은 노드 수만큼 malloc 을 하니, 이 두 줄이 나오지 않으면 어딘가에서 후위 해제나 반환값 대입을 빠뜨린 것입니다. 프로젝트를 고쳐 나갈 때마다 이 명령을 돌리는 습관을 들이세요.
11. 자주 하는 실수와 함정
이번 주에 실제로 일으켜 본 것들입니다. 각 항목의 절 번호에 증거가 있습니다.
1. 재귀 반환값을 버리기. bst_insert(root, 42); 라고만 쓰면 빈 트리에서 아무 일도 안 일어나고 노드는 누수됩니다. root = bst_insert(root, 42); 까지가 한 세트입니다. 컴파일러는 경고하지 않습니다. (5.2절)
2. 트리를 전위 순회로 해제. free(root) 뒤에 root->left 를 읽는 해제 후 사용입니다. GCC 13 이 -Wuse-after-free 로 경고하고, Valgrind 가 Invalid read 로 잡습니다. 해제는 무조건 후위. (2.7절)
3. BST 검증을 자식하고만 비교. 50 → 30 → 55 반례를 기억하세요. 조상이 정한 (최소, 최대) 범위를 물려줘야 합니다. (7.1절)
4. 정렬된 입력을 순수 BST 에 넣기. 높이가 n − 1 인 사슬이 되어 탐색이 O(n), 삽입이 O(n²) 입니다. 20,000개에 1초, 재귀 순회는 100만 개에서 스택 오버플로. 실전은 AVL 이나 레드-블랙 트리, 또는 13주차 해시 테이블. (5.5절, 4.1절)
5. AVL 회전 뒤 높이 갱신 순서. 회전으로 아래로 내려간 노드부터 갱신해야 합니다. 위 노드를 먼저 갱신하면 자식의 낡은 높이를 읽습니다. 컴파일도 실행도 되지만 균형 판단이 조금씩 틀어집니다. (8.3절)
6. 힙 인덱스 공식. 부모는 (i − 1) / 2 입니다. i / 2 로 쓰면 인덱스 2 의 부모가 1 이 되어 규칙이 깨진 힙이 만들어지는데, 대부분의 입력에서는 결과가 맞아서 알아채기 어렵습니다. (9.5절)
7. sift-down 에서 큰 자식과 교환. 최소 힙은 작은 쪽 자식과 바꿔야 합니다. 큰 쪽과 바꾸면 그 자식이 올라와 형제보다 커집니다. (9.4절)
8. 고정 크기 스택으로 반복문 순회. 64칸 배열에 65개를 쌓으면 바로 뒤의 top 을 덮어써서 조용히 틀린 결과가 납니다. 넘침 검사를 넣거나 동적 배열 스택을 쓰세요. (4.4절)
9. rm 에서 형제 사슬을 안 끊기. first-child/next-sibling 트리에서 tree_free(c) 를 그대로 부르면 뒤 형제들까지 지웁니다. c->sibling = NULL 먼저. (10절 프로젝트 1)
10. 힙 배열을 정렬된 목록으로 착각. 힙은 루트만 최솟값을 보장합니다. 순서가 필요하면 복사본에서 pop 을 반복하거나, 정렬을 하세요. (9.3절, 프로젝트 3)
12. 다음 단계
이번 주에 할 수 있게 된 것
- 트리 노드 구조체가 메모리에 어떻게 놓이는지(24바이트, 패딩 4바이트) 실제 주소로 확인했습니다.
- 순회 네 가지를 종이에서 수행할 수 있고, 각각 어디에 쓰는지(출력, 정렬, 해제, 층별) 압니다.
- 재귀 순회의 호출 스택을 우리 스택으로 바꿔 반복문으로 만들 수 있습니다.
- BST 의 삽입, 탐색, 삭제(세 경우), 검증, 이웃 찾기를 구현했고, “부분트리의 새 루트를 반환” 패턴을 손에 익혔습니다.
- 정렬된 입력이 BST 를 어떻게 망가뜨리는지 높이와 시간으로 확인했고, AVL 회전으로 어떻게 고치는지 봤습니다.
- 힙을 배열로 만들고, O(n) 우선순위 큐를 O(log n) 으로 바꿔 800배 차이를 측정했습니다.
- 폴더 구조, 수식 파서, 작업 관리자를 트리로 만들었습니다.
연습 문제
- 트리 복사.
TNode *tree_copy(const TNode *root)를 만드세요. 어느 순회가 자연스러운지 먼저 생각해 보세요. (힌트: 새 노드를 만든 뒤 자식을 복사해 붙여야 하니 전위입니다.) - 잎 개수 세기, 최대 깊이의 노드 찾기.
count_nodes와tree_height를 참고해 재귀로 만드세요. - 동적 스택으로 바꾸기. 4.4절의 고정 64칸 스택을 11주차의 동적 배열 스택으로 바꿔, 4.1절의 사슬 100만 개를 반복문 중위 순회로 순회하세요.
- 후위 순회의 반복문 버전. 전위와 중위보다 어렵습니다. 힌트: 스택 두 개를 쓰거나, “마지막으로 방문한 노드”를 기억하세요.
- BST 삭제에 선행자 쓰기. 6.3절의 실험을 코드로 완성하고, 두 방식의 결과 트리 모양을 비교하세요.
- AVL 삭제. BST 삭제 뒤 돌아오는 길에 균형을 검사하고 회전하세요. 삽입과 달리 회전이 여러 번 연쇄될 수 있습니다.
- k 번째로 작은 값. BST 에서 중위 순회를 하다가 k 번째에서 멈추면 됩니다. 카운터를 어떻게 넘길지가 문제입니다(6주차 포인터).
- heapify 와 n 번 push 의 차이 측정. 배열 100만 개를 힙으로 만들 때,
heap_push를 100만 번 하는 것과 9.6절의 heapify 한 번의 시간을 재 보세요. O(n log n) 과 O(n) 의 차이입니다. - 파서에 거듭제곱 추가.
^는 오른쪽 결합입니다.power = factor ('^' power)?처럼 규칙 자체가 오른쪽으로 재귀하면 됩니다. - 작업 관리자에 우선순위 변경. 이름으로 작업을 찾아 우선순위를 바꾼 뒤, 올라가야 하면 sift-up, 내려가야 하면 sift-down 을 부르세요.
다음 주 예고
BST 는 O(log n) 입니다. 100만 개에서 20번이면 훌륭하지만, “20번도 많다”는 사람들이 있습니다. 다음 주는 해시 테이블입니다. 평균 O(1), 즉 몇 개가 들어 있든 거의 한 번에 찾습니다. 그 마법의 원리와, 그 대가로 치러야 하는 것들(충돌, 리사이징, 정렬 순서를 잃는 것)을 배웁니다. 10주차 연결 리스트가 체이닝으로 다시 등장하고, 이번 주 BST 와 해시 테이블을 직접 대결시킵니다. 디스크를 위한 트리(B-트리)와 문자열 전용 트리(트라이)도 같은 주에 봅니다.
마치며
이번 주는 Part 2 에서 가장 밀도가 높은 주였습니다. 지난 주차들이 전부 재료로 쓰였습니다. 레벨 순회에 11주차 큐가, 반복문 순회에 11주차 스택이, 노드 크기에 8주차 패딩이, 해제 후 사용을 잡는 데 7주차 Valgrind 가, 힙 비교에 11주차 우선순위 큐가, AST 출력에 11주차 후위 표기법이 나왔습니다. 벽돌을 하나씩 쌓아 온 이유입니다.
그리고 이번 주에 가장 강조하고 싶은 것은 “부분트리의 새 루트를 반환” 패턴입니다. 삽입, 삭제, 회전, AST 만들기가 전부 이 하나로 됐습니다. 이 패턴이 손에 익으면 앞으로 만나는 어떤 트리 코드도 낯설지 않을 겁니다.
트리를 그림 없이 코딩하려 하지 마세요. 종이에 노드를 그리고 포인터가 움직이는 것을 따라가는 것이 가장 빠른 길입니다. 특히 BST 삭제의 경우 3과 AVL 의 LR 회전은 꼭 손으로 그려 보세요. 그리고 뭔가 이상하면 이번 주에 쓴 도구들, 컴파일러 경고와 Valgrind 와 AddressSanitizer 를 먼저 돌려 보세요. 트리 버그의 대부분은 해제 순서와 포인터 대입 누락이고, 도구가 정확한 줄을 알려 줍니다.
다음 주에 만나요!
체크리스트
- [ ]
sizeof(TNode)가 24인 이유를 설명할 수 있다 - [ ] 전위/중위/후위 순회를 코드 없이 종이에서 수행할 수 있다
- [ ] 순회별 용도(출력/정렬/해제/층별)를 짝지을 수 있다
- [ ] 트리 해제가 후위 순회여야 하는 이유를 설명하고, 전위로 지웠을 때 Valgrind 가 뭐라고 하는지 안다
- [ ] 레벨 순서 순회를 큐로 구현할 수 있고, 스택으로 바꾸면 왜 DFS 가 되는지 안다
- [ ] 반복문 전위 순회에서 오른쪽을 먼저 push 하는 이유를 안다
- [ ] “부분트리 루트 반환” 패턴으로 삽입을 구현하고, 반환값을 안 받으면 어떻게 되는지 안다
- [ ] BST 중위 순회 = 정렬인 이유를 설명할 수 있다
- [ ] BST 삭제 3경우를 구분하고, 후속자 대체가 규칙을 유지하는 이유를 안다
- [ ] 순진한 BST 검증의 반례 트리를 그릴 수 있다
- [ ] 정렬된 입력이 BST 높이를 n − 1 로 만드는 것을 직접 확인했다
- [ ] 균형 인수를 계산하고 LL/RR/LR/RL 을 구분할 수 있다
- [ ] 오른쪽 회전을 포인터 두 개 조작으로 그릴 수 있고, 높이 갱신 순서를 안다
- [ ] 힙의 배열 인덱스 공식 세 개를 외웠다
- [ ] sift-up/sift-down 을 구현할 수 있고, 작은 자식과 바꿔야 하는 이유를 안다
- [ ] 힙 정렬의 2단계(heapify + 추출 반복)를 설명할 수 있다
- [ ] 세 프로젝트를 빌드하고
make memcheck로 누수 0 을 확인했다 - [ ] (도전) 동적 스택으로 100만 노드를 순회하고, 파서에 거듭제곱을 넣어 봤다
참고 자료
- CLRS (Introduction to Algorithms) — Chapter 6 (Heapsort), 12 (BST), 13 (RB-tree)
- AVL tree visualization (VisuAlgo) — 회전을 애니메이션으로 볼 수 있습니다
- Binary heap (Wikipedia)
- Recursive descent parser (Wikipedia)
- 다음 주차: 13주차 해시 테이블과 고급 트리