삭제 예시
30을 지운 뒤 가운데 리프가 비면 언더플로우를 복구해야 한다. 핵심은 같은 문제라도
재분배는 부모 경계값을 갱신하고, 병합은 부모 키 수를 줄인다는 점이다.
1. 초기
루트가 세 리프 구간을 나눈다
루트의 구분 키 `30`, `35`가 리프 범위를 나누고 있다.
2. 30 삭제
가운데 리프가 빈 상태가 된다
차수 3에서는 리프가 최소 1개 키를 가져야 하므로, 빈 리프를 그대로 둘 수 없다.
3. 복구 선택
형제 상태에 따라 두 경로로 갈린다
둘 다 빈 리프를 없애는 과정이지만, 부모에 남는 흔적은 다르다.
재분배
형제에 여유 키가 있으면 하나를 빌려 와서 빈 리프를 다시 채운다.
병합
빌려줄 키가 없으면 빈 리프를 없애고 형제와 합치며 부모 구분 키도 삭제한다.
같은 원인, 다른 결과: 둘 다 리프 언더플로우를 복구하지만,
재분배는 부모가 경계값만 수정하고 끝나며 병합은 부모 키 수 자체를 줄여
상위로 영향이 이어질 수 있다.
빈 리프가 다시 최소 키 수를 만족하고, 부모 구분 키는 새 경계에 맞춰 바뀐다.
리프
`[10, 20]`이 `[10]`이 되고, 빈 리프가 `[20]`으로 복구된다.
부모
구분 키 `30`은 더 이상 경계가 아니므로 `20`으로 갱신된다.
빈 리프를 유지하지 않고 형제와 하나로 합치며, 부모도 구분 키 하나를 잃는다.
리프
빈 리프가 사라지고 두 리프만 남아 구조가 더 압축된다.
부모
구분 키 `30`이 삭제되어 루트가 `[35]`만 남는다. 이 감소는 위로 전파될 수 있다.