b-tree에서 요소를 어떻게 제거합니까?

Question

나는 b-tree에 대해 배우려고 노력 중이며 모든 소스는 b-tree 속성을 유지하면서 트리에서 요소를 제거하는 방법에 대한 설명을 생략 한 것 같습니다.

누군가 알고리즘을 설명하거나 리소스가 어떻게 완료되는지 설명 할 수 있습니까?

Answer 1

위키 피 디아 페이지에 설명이 있습니다. B-tree - Deletion

Answer 2

아직 얻지 못 하셨다면 Carmen & al 알고리즘 소개 3rd Edition을 강력히 추천합니다.

작업은 자연스럽게 B-Tree 속성에서 비롯되기 때문에 설명하지 않습니다.

노드의 요소 수에 대한 하한값이 있으므로 요소를 제거하면이 불변량을 위반하는 경우 복원해야합니다. 일반적으로 이웃과 병합되거나 요소 일부를 훔치는 것이 일반적입니다. .

이웃 노드와 병합하는 경우 부모 노드의 요소를 제거해야하며 동일한 알고리즘을 트리거합니다. 그리고 당신이 위로 갈 때까지 재귀 적으로 적용하십시오.

B-Tree에는 재조정 기능이 없습니다 (적어도 내가 본 제품은 아닙니다). 그래서 레드 블랙 트리 또는 AVL 트리를 유지하는 것이 훨씬 덜 복잡해졌습니다. 제거.

Answer 3

어떤 b-trees에 대해 이야기하고 있습니까? 연결된 나뭇잎이 있거나 없습니까? 또한 항목을 삭제하는 여러 가지 방법 (상단 하단, 하단 하단 등)이 있습니다. 이 백서는 도움이 될 것입니다 : B-trees, Shadowing, and Clones (비록 파일 시스템과 관련된 많은 것들이 많더라도).

Answer 4

CLRS (제 2 판)에서 삭제 예제는 여기에 있습니다 : http://ysangkok.github.io/js-clrs-btree/btree.html

을 눌러 "초기화 책"다음 순서로 삭제 버튼을 누릅니다. 모든 경우에 해당됩니다. 각 버튼을 누르기 전에 새 트리 상태를 시도하고 예측하고 케이스가 모두 고유 한 방식으로 인식하십시오.