Deletion from a leaf node
1. search for the key to delete
2. if the key in leaf nodes, simply delete it
3. if underflow happens, rebalancing
Rebalancing starts from a leaf toward the root until the tree is balanced.
Triggered when underflow happens through remove()
typeswitch(node) {
case when match(Leaf) {
if canMerge(R to L)
merge a deficient node R into left-sibling node L (append)
remove R's separator from parent
else
merge a deficient node L onto right-sibling node R (prepend)
remove L's seperator from parent
# It may be propagated to branch's rebalancing
}
case when match(Root) {
if root has only 1 child
mark the child as root
}
case when match(Branch) {
if canMerge(R to L)
move R's seperator S from parent to L (append)
merge entries in R into L (append)
else merge a deficient node L onto right-sibling node R
move L's seperator S from parent to R (prepend)
merge entries in L into R (prepend)
}
}
Marge Leaf (R → L)
Marge Leaf (L → R)
Delete root
Merge branch (R → L)
images are taken from https://hazm.at/mox/algorithm/structural-algorithm/b-plus-tree.html