사용 개념: B-트리 삽입의 두 절차와 B-트리 노드 쪼개기.

“이 트리에 키를 넣은 결과를 그려라”는 문제는 같은 하위목표를 뿌리부터 되풀이한다. ① 뿌리 확인: 뿌리가 가득 찼으면 먼저 쪼갠다(새 뿌리가 생기고 높이가 1 늘어난다) ② 자식 고르기: 지금 노드의 키와 견주어 내려갈 자식을 고른다 ③ 가득 찼나 확인: 그 자식이 가득 찼으면 내려가기 전에 쪼개고, 올라온 키와 견주어 두 조각 가운데 하나를 고른다 ④ 잎에 넣기: 잎에 닿으면 정렬된 자리에 끼워 넣는다. ②와 ③은 잎에 닿을 때까지 되풀이한다.

가득 찬 노드는 키가 \(2t - 1\)개인 노드다. \(t = 2\)면 3개, \(t = 3\)이면 5개다. 트리를 한 줄로 적을 때는 층을 /로, 부모가 다른 묶음을 |로 가른다.

문제 1 · 완전한 풀이

최소 차수 \(t = 3\)인 아래 트리에 B와 Q를 차례로 넣는다.

                [G M P X]
    +-------+-----+--------+--------+
[A C D E] [J K] [N O] [R S T U V] [Y Z]

B 넣기

  1. 뿌리 확인: 뿌리 [G M P X]는 키가 4개다. 가득 차지 않았으니 그대로 둔다.
  2. 자식 고르기: B는 G보다 작다. 첫째 자식 [A C D E]로 간다.
  3. 가득 찼나 확인: 키가 4개라 가득 차지 않았다. 쪼개지 않는다.
  4. 잎에 넣기: A와 C 사이에 넣어 [A B C D E]가 된다.

Q 넣기

  1. 뿌리 확인: 뿌리는 여전히 키 4개다. 그대로 둔다.
  2. 자식 고르기: Q는 P와 X 사이다. 넷째 자식 [R S T U V]로 간다.
  3. 가득 찼나 확인: 키가 5개라 가득 찼다. 먼저 쪼갠다. 가운데 키 T가 뿌리로 올라가 [G M P T X]가 되고, 잎은 [R S]와 [U V]로 갈린다. Q는 T보다 작으니 왼쪽 조각 [R S]를 고른다.
  4. 잎에 넣기: R 앞에 넣어 [Q R S]가 된다.
                 [G M P T X]
     +--------+-----+------+------+-----+
[A B C D E] [J K] [N O] [Q R S] [U V] [Y Z]
검증 — 15_b-tree-insert_impl.py

문제 2 · 마지막 하위목표만 빈칸

\(t = 2\)인 [20] / [10] [30 40 50]에 45와 35를 차례로 넣는다.

45 넣기

  1. 뿌리 확인: 뿌리 [20]은 키가 1개다. 그대로 둔다.
  2. 자식 고르기: 45는 20보다 크다. 둘째 자식 [30 40 50]으로 간다.
  3. 가득 찼나 확인: 키가 3개라 가득 찼다. 쪼갠다. 가운데 키 40이 뿌리로 올라가 [20 40]이 되고, 잎은 [30]과 [50]으로 갈린다. 45는 40보다 크니 오른쪽 조각 [50]을 고른다.
  4. 잎에 넣기: [45 50]이 된다. 트리는 [20 40] / [10] [30] [45 50]이다.

35 넣기

  1. 뿌리 확인: 뿌리 [20 40]은 키가 2개다. 그대로 둔다.
  2. 자식 고르기: 35는 20과 40 사이다. 둘째 자식 [30]으로 간다.
  3. 가득 찼나 확인: 키가 1개라 가득 차지 않았다.
  4. 잎에 넣기: __
답

30 뒤에 넣어 [30 35]가 된다. 트리는 [20 40] / [10] [30 35] [45 50]이다.

문제 3 · 하위목표 절반이 빈칸

\(t = 2\)인 [10 20 30] / [5] [15] [25] [35 40 45]에 50과 12를 차례로 넣는다.

50 넣기

  1. 뿌리 확인: __
  2. 자식 고르기: 50은 20보다 크니 [30]으로, 다시 30보다 크니 [35 40 45]로 간다.
  3. 가득 찼나 확인: __
  4. 잎에 넣기: [45 50]이 된다.

12 넣기

  1. 뿌리 확인: 뿌리 [20]은 키가 1개다. 그대로 둔다.
  2. 자식 고르기: __
  3. 가득 찼나 확인: 지나는 노드 가운데 가득 찬 것이 없다.
  4. 잎에 넣기: __
답

50 넣기

  • 뿌리 확인: 뿌리 [10 20 30]은 키가 3개라 가득 찼다. 먼저 쪼갠다. 가운데 키 20이 새 뿌리가 되고 [10]과 [30]으로 갈린다. 높이가 1에서 2로 늘어난다. 이때의 트리는 [20] / [10] [30] / [5] [15] | [25] [35 40 45]이다.
  • 가득 찼나 확인: [30]은 가득 차지 않았다. 그 아래 잎 [35 40 45]는 키가 3개라 가득 찼다. 쪼개면 40이 [30]으로 올라가 [30 40]이 되고, 잎은 [35]와 [45]로 갈린다. 50은 40보다 크니 [45]를 고른다.

12 넣기

  • 자식 고르기: 12는 20보다 작으니 [10]으로, 다시 10보다 크니 둘째 자식 [15]로 간다.
  • 잎에 넣기: 15 앞에 넣어 [12 15]가 된다.

끝난 트리는 이렇다.

          [20]
    +----------------+
  [10]            [30 40]
 +-----+        +----+-----+
[5] [12 15]   [25] [35] [45 50]

문제 4 · 독립 문제

\(t = 3\)인 빈 B-트리에 10, 20, 30, …, 120을 작은 것부터 차례로 넣는다. 끝난 트리를 그리고, 쪼개기가 몇 번 일어났는지와 트리의 높이를 쓰라. 잎마다 키가 몇 개씩 들어 있는지 보고 까닭을 말하라.

답 
           [30 60 90]
   +-------+-------+----------+
[10 20] [40 50] [70 80] [100 110 120]

쪼개기는 3번이고 높이는 1이다.

  • 10~50을 넣으면 뿌리 하나에 키 5개가 차서 가득 찬다.
  • 60을 넣을 때 뿌리가 가득 찼으니 먼저 쪼갠다(1번째). 30이 새 뿌리가 되고 [30] / [10 20] [40 50 60]이 된다.
  • 90을 넣을 때 맨 오른쪽 잎 [40 50 60 70 80]이 가득 찼으니 쪼갠다(2번째). 60이 올라가 [30 60] / [10 20] [40 50] [70 80 90]이 된다.
  • 120을 넣을 때 맨 오른쪽 잎 [70 80 90 100 110]이 가득 찼으니 쪼갠다(3번째). 90이 올라간다.

맨 오른쪽 잎을 뺀 잎은 모두 키가 2개, 곧 아래 한계 \(t - 1\)개뿐이다. 넣는 키가 그때까지의 키보다 늘 크니 새 키는 맨 오른쪽 잎으로만 간다. 쪼개진 왼쪽 조각에는 그 뒤로 키가 더 들어오지 않아 \(t - 1\)개로 남는다.

검증 — 15_b-tree-insert_impl.py