📚 지식 노트

(1) 잎은 C, E, G, H, J 다섯 개. (2) F의 부모는 B, 형제는 E. (3) H의 깊이는 3, 트리 높이는 4. (4) 부분 트리 노드는 6개(B, E, F, H, I, J).

잎은 자식이 없는 노드라 층과 상관없다. C는 깊이 1인데도 잎이다. 높이는 뿌리에서 가장 먼 잎까지의 간선 수라 A → B → F → I → J의 4다. 노드가 10개이니 간선은 언제나 9개(뿌리를 뺀 노드마다 부모로 가는 간선 하나)다.

높이 3인 노드는 30이고, 42의 깊이는 4다. 노드 옆 h가 각 노드의 높이다.

자식부터 답을 알아야 부모를 계산할 수 있으므로 후위 순회(왼쪽 → 오른쪽 → 자신) 순서다. 빈 자리의 높이를 −1로 두면 잎은 1 + max(−1, −1) = 0으로 자연스럽게 맞는다. 깊이는 반대로 뿌리에서 내려오며 1씩 더한다(50 → 30 → 40 → 45 → 42, 간선 4개).

간선 6개, 높이는 가장 낮으면 2, 가장 높으면 6이다. 노드 1,000개면 가장 낮게 9, 가장 높게 999다.

깊이 d 층에는 노드가 많아야 2^d개라 높이 h인 이진 트리는 많아야 2^h+1 − 1개를 담는다. 7 = 2³ − 1이라 높이 2로 꽉 차고, 1,000개는 2¹⁰ − 1 = 1,023개까지 담는 높이 9가 필요하다(⌊log₂ 1000⌋ = 9). 가장 높은 경우는 층마다 하나뿐인 한 줄로 n − 1이다. 연산 시간이 높이에 비례하므로 이 차이(9 대 999)가 곧 균형 트리가 필요한 이유다.

BST는 (가)뿐이다. (나)는 4의 왼쪽 자식 5가 4보다 커서 부모와 자식만 봐도 틀렸다.

(다)가 함정이다. 9는 부모 4보다 크니 4의 오른쪽 자식으로는 맞다. 그러나 9는 8의 왼쪽 부분 트리에 있으므로 8보다 작아야 한다. BST 규칙은 바로 아래 자식만이 아니라 부분 트리 전체에 걸린다. 그래서 검사할 때는 노드마다 "허용 범위(하한, 상한)"를 내려보내며 확인해야 한다. 중위 순회가 2, 4, 9, 8, 12로 정렬이 깨진 것으로도 알 수 있다.

45는 40의 오른쪽 자식이 된다. 65 찾기는 50, 70, 60과 비교 3번 뒤 빈 자리에 닿아 "없음"이다.

45 > 50? 아니라 왼쪽, 45 > 30이라 오른쪽, 45 > 40이라 오른쪽인데 비어 있어 거기 단다. 찾기 실패도 높이만큼만 비교하므로 O(h)다.

뿌리는 60이고, 중위 순회는 20, 35, 40, 45, 60, 65, 70, 80이다.

30의 후계자는 오른쪽 부분 트리(40) 왼쪽 끝의 35다. 35는 잎이라 그냥 떼어 낸다. 50의 후계자는 70 → 60에서 멈춘 60인데, 60에는 오른쪽 자식 65가 있어 그 자리를 65가 메운다. 후계자에게 왼쪽 자식이 없다는 사실 덕분에 두 경우 모두 쉬운 지우기로 끝난다.

작은 순서로 넣으면 높이 6(한 줄). 4, 2, 6, 1, 3, 5, 7처럼 가운데부터 넣으면 높이 2. 한 줄이 되는 순서는 64가지다.

한 줄이 되려면 매번 남은 값 가운데 가장 작거나 가장 큰 값을 넣어야 한다. 마지막 하나를 빼고 여섯 번 둘 중 하나를 고르므로 2⁶ = 64가지다. 5,040가지를 모두 돌려 보면 높이 2(꽉 찬 모양)는 80가지, 높이 3이 2,240가지로 가장 많다. 무작위 순서면 대개 낮지만, 이미 정렬된 데이터가 들어오는 흔한 경우가 하필 최악이라는 것이 BST의 약점이다.

(가) LL: 30에서 오른쪽 회전. (나) LR: 10에서 왼쪽 회전 뒤 30에서 오른쪽 회전. (다) RR: 10에서 왼쪽 회전. (라) RL: 30에서 오른쪽 회전 뒤 10에서 왼쪽 회전.

곧은 줄은 회전 한 번, 꺾인 줄은 먼저 아래 자식에서 돌려 곧은 줄로 편 뒤 한 번 더 돈다. 네 경우 모두 결과는 가운데 값 20이 뿌리, 10과 30이 양쪽 자식인 같은 모양이다. 아래는 (라) RL 경우의 두 번 회전이다.

20이 뿌리가 되고 40은 20의 오른쪽 자식으로 내려간다. 30이 20의 오른쪽에서 40의 왼쪽으로 옮겨 가고, 중위 순회는 10, 20, 30, 40, 50 그대로다.

30은 20보다 크고 40보다 작으니 "20의 오른쪽"이든 "40의 왼쪽"이든 크기 순서상 같은 자리다. 바뀌는 포인터는 20.right, 40.left, 그리고 부모가 가리키던 뿌리 셋뿐이라 O(1)이고, 순서를 깨지 않으므로 BST 규칙도 그대로다.

30을 넣을 때 10에서 RR, 28을 넣을 때 30에서 LR, 27을 넣을 때 20에서 RL, 5를 넣을 때 20에서 LL. 마지막 뿌리는 25다.

넣은 값에서 뿌리 쪽으로 올라가며 처음 만나는 ±2 노드만 고치면 된다. 마지막 트리는 25 아래 10(5, 20)과 28(27, 30)로 높이 2다. 같은 값을 그냥 BST에 넣었다면 10 → 20 → 30 → 25 → 28 → 27로 높이 5가 됐다.

가장 낮으면 19, AVL은 28 이하, 레드-블랙은 39 이하, 한 줄 BST는 999,999다. log₂ 1,000,000 ≈ 19.93이라 ⌊19.93⌋ = 19, 1.44 × 19.93 ≈ 28.7, 2 × log₂ 1,000,001 ≈ 39.9다.

찾기 비교는 높이 + 1번 이하이므로 균형 트리는 최악에도 20~40번, 한 줄 BST는 최악 100만 번이다. AVL과 레드-블랙의 차이(28 대 39)는 한 자릿수 배수도 안 되지만, 균형이 없을 때와의 차이는 수만 배다. 그래서 "어떤 균형 트리냐"보다 "균형이 있느냐"가 훨씬 중요하다.

[40] → [60] → [50]을 거쳐 3번 읽고, 잎에도 55가 없어 "없음"이다. 열쇠 2개인 노드는 자식이 3개다.

55 > 40이라 40 오른쪽 틈의 자식, 55 < 60이라 60 왼쪽 틈의 자식으로 간다. 열쇠 k개가 수직선을 k+1개 구간으로 나누고 구간마다 자식이 하나씩이라 자식은 k+1개다. 모든 잎이 같은 깊이에 있으니 어느 열쇠를 찾든 읽기 횟수는 층 수와 같다.

갈라지기는 4번(80, 30을 넣을 때 한 번씩, 90을 넣을 때 잎과 뿌리 연달아 두 번), 마지막 트리는 3층이다. 뿌리 [50], 둘째 층 [20]·[80], 잎 [10]·[30, 40]·[60, 70]·[90]이다.

뿌리가 갈라질 때만 층이 늘어(80과 90을 넣을 때) 3층이 됐다. 마지막 40과 70은 빈칸이 있는 잎에 그냥 들어간다. 갈라짐이 위로 번지는 일은 드물어, 넣기 한 번의 평균 비용은 거의 잎 하나 고치기다.

꽉 차면 4층, 최소로 차도 5층이면 충분하다. 균형 이진 트리는 30층이 필요하다.

꽉 찬 L층 트리는 열쇠를 200^L − 1개 담는다. 3층은 약 800만 개라 모자라고 4층은 약 16억 개라 넉넉하다. 최소로 찬 경우 뿌리는 자식 2개, 나머지는 100개씩이라 L층이면 적어도 2 × 100^L−1 − 1개가 들어간다. 5층의 최소가 약 2억, 6층의 최소가 약 200억이니 10억 개는 5층을 넘을 수 없다. 이진 트리는 ⌈log₂(10억 + 1)⌉ = 30층이다. 디스크 읽기 30번과 4~5번(윗층은 캐시에 있어 실제로는 1~2번)의 차이가 데이터베이스 색인이 B-트리인 이유다.

(가)와 (다)가 최소 힙이고 (나)는 아니다. (가)에서 1번 칸의 자식은 3·4번 칸(7과 4), 5번 칸의 부모는 2번 칸(2)이다.

i번 칸의 자식은 2i+1·2i+2번, 부모는 ⌊(i−1)/2⌋번이다. (나)의 4번 칸 1의 부모는 ⌊3/2⌋ = 1번 칸의 4라 조건이 깨졌다. (다)처럼 오름차순으로 정렬된 배열은 늘 최소 힙이지만, 거꾸로 힙이라고 정렬돼 있지는 않다((가)의 3과 2처럼 형제 사이에는 순서가 없다).

넣은 직후 [1, 2, 3, 6, 7, 8], 두 번 꺼낸 뒤(1과 2가 나옴) [3, 6, 7, 8]이고, 바꾸기는 모두 7번이다.

넣기 쪽 바꾸기가 4번(2가 한 번, 1이 두 번, 3이 한 번 올라감), 꺼내기 쪽이 3번(8이 두 층, 7이 한 층 내려감)이다. 어느 연산도 높이(여기서는 2)보다 많이 바꾸지 않는다. 그것이 O(log n)의 뜻이다.

마지막 힙은 [10, 15, 12]이고, 가장 큰 3개는 10, 12, 15다. 뿌리가 "3등"이라 새 값과 한 번만 비교하면 들일지 버릴지 정해지므로 최소 힙을 쓴다.

7은 3등(8)보다 작아 들어올 자격이 없으니 비교 한 번으로 버린다. 힙 크기가 k로 고정이라 값 하나에 O(log k), 전체 n개에 O(n log k)다. 모든 값을 정렬하는 O(n log n)보다 싸고, 메모리도 k칸이면 된다. 로그에서 "가장 느린 요청 상위 100개"를 고르는 일이 이렇다.

노드는 10개다. "te"는 낱말이 아니고 "in"은 낱말이다. "te"로 시작하는 낱말은 tea, ted, ten이다.

"te" 노드는 길 위에 있지만 끝 표시가 없다. 반대로 "in"은 자식(inn)이 있어도 끝 표시가 있어 낱말이다. 그래서 트라이 노드에는 자식 표 말고도 끝 표시 하나가 꼭 필요하다. 글자 수는 모두 2 + 3 × 3 + 2 + 3 = 16개인데 노드는 뿌리 빼고 9개뿐이다. 앞부분을 함께 쓰기 때문이다.

새 노드는 차례로 3, 1, 1, 1, 2, 0개(뿌리까지 모두 9개)이고, "te" 검색 결과는 tea, ten, tent다.

새 노드 수는 "이미 있는 낱말과 겹치지 않는 뒷부분의 길이"다. tent는 ten 길을 3글자 함께 쓰고 t 하나만 더한다. 마지막 t는 노드를 하나도 만들지 않고 이미 있던 t 노드에 끝 표시만 단다.

11개에서 8개로 준다. te 아래 s → t가 "st" 하나로, to 아래 a → s → t가 "ast" 하나로 합쳐진다.

t와 e는 자식이 하나지만 합칠 수 없다. t 아래는 e와 o 두 갈래이고, e도 a와 s 두 갈래이기 때문이다. a는 자식이 m 하나뿐이지만 "tea"의 끝이라 합치면 tea를 잃는다. 노드가 줄면 포인터와 자식 표도 줄어 메모리가 크게 준다. 라우팅 표나 키-값 저장소의 색인이 이 압축 트라이를 쓰는 까닭이다.

뿌리는 31, "4–7" 노드는 22다. 고칠 노드는 5번 잎 → 4–5 → 4–7 → 0–7의 네 개이고, 뿌리는 26이 된다.

5번 칸을 구간에 품은 노드만 합이 바뀌고, 그런 노드는 층마다 하나씩이다. 모두 −5씩 고쳐 22 → 17, 31 → 26이 된다. 층 수가 log₂ n + 1이니 갱신은 O(log n)이다.

통째로 쓰는 노드는 [1, 1]·[2, 3]·[4, 5] 세 개이고 답은 1 + 5 + 14 = 20이다. 들여다보는 노드는 9개다.

칸 다섯 개를 하나씩 더하는 대신 미리 더해 둔 노드 세 개를 더했다. 배열이 길어져도 걸치는 노드는 층마다 많아야 둘이라, 들여다보는 노드 수는 O(log n)에 머문다.

t = [3, 4, 4, 9, 5, 14, 2, 31]. 앞 6칸 합은 t[6] + t[4] = 14 + 9 = 23. 3~7번 합은 앞 7칸 합 25 − 앞 2칸 합 4 = 21. 3번 칸을 바꾸면 t[3], t[4], t[8]을 고친다.

6 = 110₂에서 가장 낮은 1비트(2)를 빼면 4 = 100₂, 또 빼면 0이라 두 칸이면 끝난다. 갱신은 거꾸로 3 = 011₂에 lowbit 1을 더해 4, 4에 4를 더해 8로 올라간다. 펜윅 트리는 "앞에서부터의 합"만 직접 주므로 구간 합은 두 앞부분 합의 차로 구한다. 그래서 빼기가 되는 연산(합)에는 쓰지만, 빼기가 없는 최솟값에는 세그먼트 트리를 쓴다.