6. Fortgeschrittene Datenstrukturen (12 Punkte)

6.2 · \(t=2 B-\)t=2 B-트리 · 16, 30, 40 순차 삽입

선행지식이 전혀 없어도 이 페이지 하나에서 용어를 배우고, 작은 예제를 거쳐 실제 시험 풀이와 검산까지 따라가도록 구성했습니다.

  1. 용어: 기호와 전제
  2. 직관: 비유와 작은 예
  3. 풀이: 실제 상태 변화
  4. 확인: 검산과 자가점검

자료의 성격과 정확성 경계

문제 문언·배점·후보 그림은 비공식 SoSe 2025 복기 lines 270-295와 연결 이미지에서 가져왔습니다. 정의와 수치 convention은 Lecture 04 pp.3-5, 45-46, p.57, p.114, pp.122-126으로 교차 확인했습니다. Sheet06-Sol은 RB/AVL, Sheet08-Sol은 B-Tree 삽입을 뒷받침하며, 일반 교재의 NIL-inclusive black count를 강의 SH 수치와 섞지 않습니다.

문제를 읽기 전에 알아둘 기호와 용어

기호를 모른 채 풀이를 외우지 않도록, 이 문제에서 실제로 쓰는 뜻과 작은 예를 먼저 확인합니다.

기호·용어뜻작은 예
항목 (R / rectangle)복기 그림에서 red node를 뜻하는 사각형입니다. 기호를 다른 색 의미로 재정의하지 않습니다.Tree 1의 root 27은 rectangle이므로 red입니다.
항목 (B / circle)복기 그림에서 black node를 뜻하는 원입니다. CSS 색만이 아니라 shape와 R/B label을 함께 읽습니다.Tree 3의 root 13은 black circle입니다.
\(\text{SH}(\text{nil})=0\)SH(nil)=0NIL sentinel은 black으로 모델링하지만 강의 Schwarzhöhe 수치에서는 nil 자체에 1을 더하지 않습니다.Tree 3의 root-to-terminal black 수는 3이지 4가 아닙니다.
\(t=2\)t=2B-Tree의 Grad 또는 minimum degree이며 non-root node의 key 수는 t-1부터 2t-1입니다.\(t=2\)t=2이면 한 node는 1~3 keys를 가집니다.
\(B(v)=\text{hR}-\text{hL}\)B(v)=hR-hL강의의 AVL balance factor로 오른쪽 subtree 높이에서 왼쪽 높이를 뺍니다.\(B(v)=-2\)B(v)=-2이면 이 convention에서는 left-heavy입니다.
실패AVL 검사 중 이미 균형 위반을 찾았다는 별도 반환값이며 유효한 높이 -1과 혼동하지 않습니다.empty tree는 height -1, invalid subtree는 FAIL입니다.

먼저 문제의 정체를 줄글로 이해하기

B-Tree node는 여러 sorted key와 여러 child interval을 가집니다. 최소차수 \(t=2\)t=2이면 non-root node는 1~3개의 key를 가질 수 있고 full node는 \(2t-1=3\)2t-1=3개입니다.

강의의 top-down insertion은 full node 안으로 내려가지 않습니다. child가 full이면 먼저 median을 parent로 올려 split한 뒤 올바른 half로 내려갑니다.

초기 root [5,20,25]가 이미 full이므로 16을 넣기 전에 root부터 split해야 합니다.

필요한 개념을 깊게 배우기

개념 1

0단계 · \(t=2\)t=2용량

각 node는 최대 3 keys, root가 아닌 node는 최소 1 key입니다. 내부 node에 k keys가 있으면 k+1 children이 key interval을 담당합니다.

모든 leaves는 같은 depth에 있어야 합니다.

수식으로 정확히 쓰기

\[\min \text{keys}=t-1=1\]min keys=t-1=1
\[\max \text{keys}=2t-1=3\]max keys=2t-1=3
\[\text{children}=k+1\]children=k+1
개념 2

1단계 · split

full [a,b,c]를 split하면 median b가 parent로 올라가고 left [a], right [c]가 됩니다. leaf가 아니라면 child pointers도 앞 t개와 뒤 t개로 나눕니다.

split은 key를 복사해 남기는 것이 아니라 median을 parent로 이동시킵니다.

수식으로 정확히 쓰기

\[[a,b,c] \Rightarrow [a] ↑b [c]\][a,b,c] ⇒ [a] ↑b [c]
개념 3

2단계 · 루트 분할(root split)

초기 root [5,20,25]를 split해 새 root [20], left internal [5], right internal [25]를 만듭니다.

기존 네 leaf children은 [5] 아래 두 개와 [25] 아래 두 개로 정확히 분배합니다.

수식으로 정확히 쓰기

\[\text{new} \text{루트}=[20]\]new root=[20]
개념 4

3단계 · 삽입 실행 시간(runtime)

각 level에서 node 안 key 위치를 찾고 필요하면 constant-number pointer split을 수행하며 height만큼 내려갑니다. 강의 RAM 모델에서는 \(O(t\cdot h)\)O(t·h), 고정 t이면 \(O(\log n)\)O(log n)입니다.

B-Tree는 node를 disk block에 맞춰 큰 t로 사용해 I/O 횟수를 줄이는 목적도 있습니다.

수식으로 정확히 쓰기

\[h=\Theta(\log_{t} n)\]h=Θ(logₜ n)
\[\text{insert}=O(t\cdot h)\]insert=O(t·h)
초보자용 연결 강의

이 소문제를 왜 배우나

B-Tree는 한 node에 key가 여러 개 있고 child도 여러 개라 binary tree와 읽는 법이 다릅니다. capacity, interval, preemptive split을 함께 이해해야 key를 4개로 overflow시키지 않고 각 삽입 뒤 올바른 multiway structure를 그릴 수 있습니다.

풀이 전에 꼭 알아야 할 말

B-Tree node와 key interval

한 node의 sorted keys가 수직 경계처럼 child 구간을 나눕니다. k keys를 가진 internal node는 k+1 children을 가지며 각 child의 모든 key가 해당 interval 안에 있어야 합니다.

아주 작은 예: [25,30]은 \(\text{children} (<25), (25,30), (>30)\)children (<25), (25,30), (>30)세 개를 가집니다.

\(\text{Grad} t=2\)Grad t=2와 full

non-root node는 최소 \(t-1=1,\)t-1=1,최대 \(2t-1=3 \text{keys}\)2t-1=3 keys입니다. 3 keys인 node는 valid하지만 full이라 그 안으로 더 내려가기 전 split해야 합니다.

아주 작은 예: [26,30,50]은 overflow가 아니라 full이고 다음 40 전에 split합니다.

split과 promotion

full [a,b,c]의 median b를 parent로 이동시키고 [a]와 [c] 두 node를 만듭니다. median을 child에 복사해 남기지 않으며 child pointers도 두 묶음으로 나눕니다.

아주 작은 예: [26,30,50] → [26] ↑30 [50]입니다.

모든 leaves 같은 depth

B-Tree는 balanced multiway search tree라 어느 leaf까지 내려가도 depth가 같습니다. root split은 새 root를 만들어 모든 기존 leaf depth를 동시에 한 단계 늘립니다.

아주 작은 예: 한쪽 branch만 더 깊어지도록 leaf child를 임의로 추가하면 invalid입니다.

칸막이가 있는 서랍장

한 서랍 안의 key는 물건 번호 구간을 나누는 칸막이입니다. 서랍이 가득 차면 가운데 칸막이를 위 안내판으로 올리고 양쪽 서랍으로 나눕니다. 그런 다음 목표 번호가 어느 새 구간인지 다시 보고 내려갑니다.

서랍 안의 번호 칸막이
↔
sorted keys in node
칸막이 사이의 물건 보관 구역
↔
child intervals
가운데 칸막이를 상위 안내판으로 올림
↔
median promotion
가득 찬 서랍을 먼저 둘로 나눈 뒤 물건을 넣음
↔
split-before-descent

비유의 한계: 실제 서랍은 칸막이를 복사할 수 있지만 B-Tree split은 median key를 parent로 이동해 child에는 남기지 않습니다. 또한 모든 leaf depth invariant는 물리적 서랍 비유만으로 보장되지 않습니다.

연결선이 있는 6-frame split sequence

1–2: \(\text{루트} \text{full} \to \text{split}\)root full → split20이 promotion되고 [5], [25]가 새 root의 children이 됩니다.
3–4: 16,30 삽입interval을 따라 두 leaf가 각각 [15,16,17], [26,30,50]이 됩니다.
5–6: \(\text{child} \text{split} \to 40\)child split → 4030 promotion 뒤 새 \((>30) \text{child} [50]\)(>30) child [50]에 40을 넣어 [40,50]을 만듭니다.

각 SVG는 connector를 먼저 그린 뒤 node box를 올립니다. promotion key는 amber, target insertion은 green, 위험한 full node는 red border로 표시합니다.

먼저 작은 예제로 연습 · root [10,20,30]에 25 삽입

\(t=2\)t=2이고 leaf root [10,20,30]이 full인 가장 작은 B-Tree에 key25를 삽입합니다.

full root 확인

\(3=2t-1 \text{keys}\)3=2t-1 keys이므로 25를 직접 넣으면 4 keys overflow가 됩니다.

[10,20,30] FULL
루트 분할(root split)

median20을 새 root로 올리고 children [10]과 [30]을 만듭니다.

[10] ← \([20] \to [30]\)[20] → [30]
25의 interval 선택

\(25>20\)25>20이므로 right child [30]으로 내려가 sorted 위치에 삽입합니다.

root[20], right[25,30]

작은 예제의 결론: top-down insertion은 full node 안으로 들어가지 않으므로 한 번 내려가는 동안 어떤 node도 4 keys가 되지 않습니다.

이제 실제 시험 문제에 연결

16 전에 가장 먼저 해야 할 일은 무엇인가?

초기 root [5,20,25]가 full이므로 median20을 새 root로 promotion하고 [5]와 [25]로 split합니다.

16은 어느 child interval로 가는가?

\(16<20\)16<20이고 \(16>5\)16>5이므로 [5] internal node의 right child [15,17]에 들어가 [15,16,17]이 됩니다.

30 삽입 뒤 무엇이 full이 되는가?

\(30>20,30>25\)30>20,30>25라 leaf [26,50]에 들어가 [26,30,50]이 되고 이 leaf가 full이 됩니다.

40을 넣기 전에 왜 split하는가?

내려갈 child [26,30,50]이 이미 3 keys full이므로 직접 40을 넣지 않고 median30을 parent로 먼저 올립니다.

promotion 뒤 40의 최종 위치는 어디인가?

parent [25,30]에서 \(40>30\)40>30이라 new right child [50]을 선택하고 sorted insert해 [40,50]을 만듭니다.

최종 tree를 어떻게 검산하는가?

모든 node key 정렬, 1~3 keys, k+1 children, 동일 leaf depth, child interval order 다섯 항목을 검사합니다.

답이 맞는지 스스로 검산

  • 여섯 microstate 각각에서 node key가 sorted이고 key 수가 1~3인지 검사합니다.
  • internal node마다 children 수가 keys 수+1이고 모든 child key가 parent가 정의한 interval 안에 있는지 재귀 검증합니다.
  • 모든 leaf depth가 동일하며 promotion20과30이 원래 child에 중복으로 남지 않았는지 확인합니다.

30초 자가점검

[26,30,50]에 40을 먼저 넣어 네 key 뒤 split해도 되는가?

힌트: 강의의 Suchen und Splitten 순서를 떠올립니다.

정답: 아닙니다. 내려갈 child가 full이면 먼저 split하고 promotion 뒤 target을 다시 비교해 한 half로 내려갑니다.

[26,30,50] split에서 parent로 올라가는 key는 무엇인가?

힌트: sorted 세 key의 가운데를 고릅니다.

정답: median 30입니다. children은 [26]과 [50]이 되고 30은 parent [25]에 들어가 [25,30]이 됩니다.

마지막에 쓰는 시험 답안 틀

\(t=2\)t=2이므로 max 3 keys. 먼저 full root [5,20,25]를 split해 root [20], children [5],[25]를 만든다. \(16\to [15,16,17], 30\to [26,30,50]. 40\)16→[15,16,17], 30→[26,30,50]. 40삽입 전 이 full leaf를 split해 30을 parent로 올리고 [40,50]에 삽입한다.

자주 하는 실수

근거와 정확성 범위

복기 문언, 강의 정의, 공식 연습 풀이, 추가 유도를 구분해 표시합니다.

마지막 생성: 2026-08-02 08:51