B-Tree 하위 트리를 제거하는 방법

Question

B- 트리를 사용하는 데이터 구조를 구현하고 있습니다. 나무의 일부를 제거하는 방법이 필요합니다.

특히, 트리에 저장된 항목의 번호가 0에서 n-1 인 것으로 가정합니다. 주어진 서브 블록 (i, j)은 0, .., i-1, j + 1, .. n-1을 포함하는 유효한 B- 트리를 남겨 두어야 만한다.

기본 경우는 i 번째와 j 번째 항목이 모두 동일한 리프 노드에있는 경우입니다. 쉽습니다. L_i가 i 번째 엔트리를 포함하는 리프 노드이고, L_j가 j 번째 엔트리를 포함하는 리프 노드이고, lca (L_i, L_j)가 L_i 및 L_j의 가장 낮은 공통 조상 인 내부 노드라고 가정한다. 어떻게 진행해야합니까?

도움을 주시면 감사하겠습니다.

Answer 1

귀하는 귀하의 구체적인 어려움을 진술하지 않았지만 그것은 정상적인 삭제 과정의 특별한 경우 일뿐입니다. 키를 삭제하고 노드가 너무 비어있는 경우 요소를 인접 노드에서 회전시키고 필요한 경우 병합하고 필요에 따라 부모 노드를 조정합니다.