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)
}
}
avoided borrowing
https://cs.stackexchange.com/questions/63170/is-promoting-a-key-a-part-of-deleting-internal-node-key-in-b-tree
Quote from prefix b-tree paper for Deletion and underflow
