사용 개념: B-트리 삭제의 네 경우. 이 수업의 방식(잎에서 지우고, 모자라면 위로 올라가며 고친다)으로 푼다.
“이 트리에서 키를 지운 결과를 그려라”는 문제는 같은 하위목표의 되풀이다. ① 자리 찾기: 지울 키가 잎에 있는지 내부 노드에 있는지 본다. 내부 노드면 선행 키를 그 자리에 올리고 잎에서 선행 키를 지운다 ② 잎 확인: 키를 뺀 잎에 \(t - 1\)개 이상 남았으면 끝이다 ③ 빌리기: 모자라면 왼쪽 형제, 오른쪽 형제 순서로 키가 \(t\)개 이상인 형제를 찾아 빌린다. 형제의 키는 부모로 올라가고 부모의 키가 내려온다 ④ 합치기: 두 형제 모두 \(t - 1\)개뿐이면 부모의 키 하나를 내려 형제와 합친다(왼쪽 형제가 있으면 왼쪽과) ⑤ 부모 확인: 합쳤으면 부모로 올라가 ②부터 다시 본다. 뿌리의 키가 0개가 되면 합친 노드가 새 뿌리다.
네 문제 모두 최소 차수 \(t = 2\)다. 뿌리가 아닌 노드는 키가 적어도 1개 있어야 하고, 형제가 키를 빌려주려면 2개 이상 가지고 있어야 한다.
문제 1 · 완전한 풀이
아래 트리에서 32, 31, 30을 차례로 지운다.
[20 40]
+-----------------+-------------------+
[10] [30 33] [50 60]
+----+ +-------+------+ +----+----+
[5] [15] [25 28] [31 32] [35] [45] [55] [65]
32 지우기
- 자리 찾기: 32는 잎 [31 32]에 있다.
- 잎 확인: 지우면 [31]로 키가 1개 남는다. 아래 한계를 지키니 끝이다(경우 1-1).
31 지우기
- 자리 찾기: 31은 잎 [31]에 있다.
- 잎 확인: 지우면 키가 0개다. 모자라다.
- 빌리기: 왼쪽 형제 [25 28]은 키가 2개라 빌릴 수 있다. 형제의 가장 큰 키 28이 부모로 올라가고, 부모의 30이 빈 잎으로 내려온다(경우 1-2a). 부모는 [28 33], 잎은 [25], [30], [35]가 된다.
[20 40]
+--------------+----------------+
[10] [28 33] [50 60]
+----+ +----+----+ +----+----+
[5] [15] [25] [30] [35] [45] [55] [65]
30 지우기
- 자리 찾기: 30은 잎 [30]에 있다.
- 잎 확인: 지우면 키가 0개다. 모자라다.
- 빌리기: 왼쪽 형제 [25]도 오른쪽 형제 [35]도 키가 1개뿐이다. 빌릴 수 없다.
- 합치기: 부모의 28을 내려 왼쪽 형제 [25]와 합친다. [25 28]이 된다(경우 1-2b).
- 부모 확인: 부모는 [33]으로 키가 1개 남았다. 아래 한계를 지키니 끝이다.
[20 40]
+-------------+---------------+
[10] [33] [50 60]
+----+ +------+ +----+----+
[5] [15] [25 28] [35] [45] [55] [65]
문제 2 · 마지막 하위목표만 빈칸
[20 40] / [10] [25 30 35] [50 60]에서 60, 10, 50을 차례로 지운다.
60 지우기
- 자리 찾기: 60은 잎 [50 60]에 있다.
- 잎 확인: 지우면 [50]으로 키가 1개 남는다. 끝이다(경우 1-1).
10 지우기
- 자리 찾기: 10은 잎 [10]에 있다.
- 잎 확인: 지우면 키가 0개다. 모자라다.
- 빌리기: 맨 왼쪽 잎이라 왼쪽 형제가 없다. 오른쪽 형제 [25 30 35]는 키가 3개라 빌릴 수 있다. 형제의 가장 작은 키 25가 부모로 올라가고, 부모의 20이 내려온다(경우 1-2a). 트리는
[25 40] / [20] [30 35] [50]이다.
50 지우기
- 자리 찾기: 50은 잎 [50]에 있다.
- 잎 확인: 지우면 키가 0개다. 모자라다.
- 빌리기: __
답
맨 오른쪽 잎이라 오른쪽 형제가 없다. 왼쪽 형제 [30 35]는 키가 2개라 빌릴 수 있다. 형제의 가장 큰 키 35가 부모로 올라가고, 부모의 40이 내려온다(경우 1-2a). 트리는 [25 35] / [20] [30] [40]이다.
문제 3 · 하위목표 절반이 빈칸
[30 60] / [10 20] [40] [70]에서 40, 60, 30을 차례로 지운다.
40 지우기
- 자리 찾기: 40은 잎 [40]에 있다.
- 잎 확인: __
- 빌리기: 왼쪽 형제 [10 20]은 키가 2개다. 20이 뿌리로 올라가고 뿌리의 30이 내려온다. 트리는
[20 60] / [10] [30] [70]이다.
60 지우기
- 자리 찾기: __
- 잎 확인: 선행 키를 내준 잎이 비었다. 모자라다.
- 빌리기: 왼쪽 형제 [10]도 오른쪽 형제 [70]도 키가 1개뿐이다. 빌릴 수 없다.
- 합치기: __
- 부모 확인: 부모는 뿌리이고 키가 1개 남았다. 끝이다.
30 지우기
- 자리 찾기: 30은 뿌리에 있다. 내부 노드다. 30의 왼쪽 자식 [10 20]에서 가장 큰 키 20이 선행 키다. 20을 뿌리에 올리고 잎에서 20을 지운다.
- 잎 확인: __
답
40 지우기
- 잎 확인: 지우면 키가 0개다. 모자라다(경우 1-2).
60 지우기
- 자리 찾기: 60은 뿌리 [20 60]에 있다. 내부 노드다(경우 2). 60의 왼쪽 자식은 잎 [30]이고 선행 키는 30이다. 30을 60 자리에 올려 뿌리가 [20 30]이 되고, 잎에서 30을 지운다.
- 합치기: 왼쪽 형제 [10]과 합친다. 부모(뿌리)에서 두 잎을 가르던 20이 내려와 [10 20]이 된다(경우 1-2b). 트리는
[30] / [10 20] [70]이다.
30 지우기
- 잎 확인: 잎은 [10]으로 키가 1개 남았다. 끝이다(경우 2 → 1-1). 트리는
[20] / [10] [70]이다.
문제 4 · 독립 문제
아래 트리에서 30, 50, 40을 차례로 지운다. 지울 때마다 거치는 경우와 결과 트리를 적어라.
[40]
+--------------+
[20] [60 80]
+----+ +----+----+
[5] [30] [50] [70] [90]
답
30 지우기: 경우 1-2b → 부모에서 1-2a(오른쪽)
잎 [30]이 빈다. 왼쪽 형제 [5]는 키가 1개뿐이고 오른쪽 형제는 없다. 부모의 20을 내려 [5 20]으로 합친다. 부모는 키가 0개가 되어 모자라다. 부모는 맨 왼쪽 자식이라 왼쪽 형제가 없고, 오른쪽 형제 [60 80]은 키가 2개라 빌릴 수 있다. 60이 뿌리로 올라가고 뿌리의 40이 내려와 부모가 [40]이 된다. 내부 노드끼리 빌렸으니 형제의 첫 자식 [50]도 따라와 [40]의 둘째 자식이 된다.
[60]
+-----------+
[40] [80]
+-----+ +----+
[5 20] [50] [70] [90]
50 지우기: 경우 1-2a(왼쪽)
잎 [50]이 빈다. 왼쪽 형제 [5 20]은 키가 2개다. 20이 부모로 올라가고 부모의 40이 내려온다.
[60]
+-----------+
[20] [80]
+----+ +----+
[5] [40] [70] [90]
40 지우기: 경우 1-2b → 부모에서 1-2b → 높이가 줄어듦
잎 [40]이 빈다. 왼쪽 형제 [5]는 키가 1개뿐이고 오른쪽 형제는 없다. 부모의 20을 내려 [5 20]으로 합친다. 부모는 키가 0개가 된다. 부모의 오른쪽 형제 [80]도 키가 1개뿐이라 빌릴 수 없다. 뿌리의 60을 내려 [80]과 합쳐 [60 80]이 된다. 뿌리의 키가 0개가 되었으니 [60 80]이 새 뿌리다. 높이가 2에서 1로 줄어든다.
[60 80]
+-----+----+
[5 20] [70] [90]