B-트리 삭제 시뮬레이터

삽입은 노드가 가득 차면 위로 갈라지지만(split), 삭제는 노드가 최소 키 개수(⌈m/2⌉−1개) 아래로 떨어지면 형제에게서 빌리거나(rotate) 형제와 합칩니다(merge). 합치기가 뿌리까지 이어지면 트리 높이가 한 층 줄어듭니다 — 삽입에서 뿌리가 갈라져 높이가 느는 것과 대칭입니다.

바로 지우지 않고, 왼쪽·오른쪽 자식 중 여유(키가 더 많은 쪽)가 있는 쪽에서 바꿔치기 키를 가져옵니다. 왼쪽에서 가져오면 그 자식의 가장 큰 키(선행자), 오른쪽에서 가져오면 가장 작은 키(후속자)입니다. 그 키를 이 자리에 놓고, 원래 있던 자식에서 다시 지웁니다.

형제 중 하나가 최소 개수보다 많이 갖고 있으면 빌립니다(부모의 갈림키를 내리고 형제의 끝 키를 부모로 올림). 양쪽 형제 모두 최소 개수뿐이면 부모의 갈림키를 끌어내려 형제와 하나로 합칩니다.

B-트리 삭제는 표준 절차라 정답 자체는 모든 교재가 같습니다. 다만 흔한 교재 설명(CLRS)은 내려가기 전에 미리 자식을 채워 두는 방식을 쓰는데, 이 사이트의 차수 규약(최대 m−1개, 최소 ⌈m/2⌉−1개)에서는 그 방식이 홀수 차수에서 노드를 최대치보다 하나 넘치게 만드는 것을 직접 재현해 확인했습니다. 그래서 실제로 최소 아래로 떨어진 뒤에만 재균형하는 방식(아래에서 위로)으로 고쳐 구현했고, 무작위 트리·무작위 삭제 순서 조합 수만 번으로 매 단계 B-트리 성질이 지켜지는지 대조했습니다.