Java Reference
In-Depth Information
48
45 4748 50 52
(A)
23
18
33
101215
18 19 20 21
22
23 30 31
45 47
48 50 52
(B)
Figure10.24 Deleting the record with key value 33 from the B + -tree of Fig-
ure 10.18 via collapsing siblings. (a) The two leftmost leaf nodes merge together
to form a single leaf. Unfortunately, the parent node now has only one child.
(b) Because the left subtree has a spare leaf node, that node is passed to the right
subtree. The placeholder values of the root and the right internal node are updated
to reflect the changes. Value 23 moves to the root, and old root value 33 moves to
the rightmost internal node.
/ ** Deletearecordwiththegivenkeyvalue,and
returntrueiftherootunderflows * /
privatebooleanremovehelp(BPNode<Key,E>rt,Keyk){
intcurrec=binaryle(rt.keys(),rt.numrecs(),k);
if(rt.isLeaf())
if(((BPLeaf<Key,E>)rt).keys()[currec]==k)
return((BPLeaf<Key,E>)rt).delete(currec);
elsereturnfalse;
else//Processinternalnode
if(removehelp(((BPInternal<Key,E>)rt).pointers(currec),
k))
//Childwillmergeifnecessary
return((BPInternal<Key,E>)rt).underflow(currec);
elsereturnfalse;
}
Figure10.25 Java-like pseudocode for the B + -tree delete algorithm.
Search WWH ::




Custom Search