treeb-tree

How do I delete a key of an internal node of a B-Tree if it has children with the minimum number of keys?


I have this B-tree of order 5:

The original tree

If I want to delete the key 120, one source tells me that if both the children of the key have the minimum number of keys, then the children are merged into one node after deletion.

So the right child of 93 should be a node with the keys 96,115,125,141.

But when I created the tree and tried to delete the key 120 with this visualization tool, it gave me this tree:

Tree after deleting key 120

Can someone explain?


Solution

  • There are several algorithms to perform a deletion, so it should not be a surprise that there are several outcomes possible.

    The one described in Wikipedia - B-tree has this procedure on deleting a key from an internal node, which is your case:

    1. Choose a new separator (either the largest element in the left subtree or the smallest element in the right subtree), remove it from the leaf node it is in, and replace the element to be deleted with the new separator.

    2. The previous step deleted an element (the new separator) from a leaf node. If that leaf node is now deficient (has fewer than the required number of nodes), then rebalance the tree starting from the leaf node.

    If we apply this to your scenario, we can focus on this part of your tree:

                      ┌─────┬─────┬─────┐
                      │  85 │  93 │ 120 │
                      ├─────┼─────┼─────┤
          ┌───────────┘ ┌───┘     └───┐ └───────────┐
    ┌─────┼─────┐ ┌─────┼─────┐ ┌─────┼─────┐ ┌─────┼─────┐
    │  82 │  84 │ │  87 │  90 │ │  96 │ 115 │ │ 125 │ 141 │ 
    └─────┴─────┘ └─────┴─────┘ └─────┴─────┘ └─────┴─────┘
    

    In step 1 we identify key 115 as the new separator, as it is the largest element in the left subtree below key 120. We remove it from the leaf and replace 120 with 115:

                      ┌─────┬─────┬─────┐
                      │  85 │  93 │ 115 │
                      ├─────┼─────┼─────┤
          ┌───────────┘ ┌───┘     └┐    └─────┐
    ┌─────┼─────┐ ┌─────┼─────┐ ┌──┴──┐ ┌─────┼─────┐
    │  82 │  84 │ │  87 │  90 │ │  96 │ │ 125 │ 141 │ 
    └─────┴─────┘ └─────┴─────┘ └─────┘ └─────┴─────┘
    

    In step 2 we indeed find that the leaf with key 96 is "deficient", so a rebalancing operation is needed. Wikipedia describes that process too:

    Rebalancing starts from a leaf and proceeds toward the root until the tree is balanced. If deleting an element from a node has brought it under the minimum size, then some elements must be redistributed to bring all nodes up to the minimum. Usually, the redistribution involves moving an element from a sibling node that has more than the minimum number of nodes. That redistribution operation is called a rotation. If no sibling can spare an element, then the deficient node must be merged with a sibling.

    As neither the left nor right sibling of our deficient leaf can lose a key, we are in that latter case, the deficient node must be merged.

    The procedure for that is described as follows:

    ...if both immediate siblings have only the minimum number of elements, then merge with a sibling sandwiching their separator taken off from their parent

    We can merge with the node at the left of 96, sandwiching separator 93:

                      ┌─────┬─────┐
                      │  85 │ 115 │
                      ├─────┼─────┤
          ┌───────────┘     └─┐   └───────────────┐
    ┌─────┼─────┐ ┌─────┬─────┼─────┬─────┐ ┌─────┼─────┐
    │  82 │  84 │ │  87 │  90 │  93 │  96 │ │ 125 │ 141 │ 
    └─────┴─────┘ └─────┴─────┴─────┴─────┘ └─────┴─────┘
    

    And this is the result you see in the simulator.

    What you described as a merge operation, would also be valid: it requires an extra check, as it can only be done when the merged leaf would not overrun the maximum capacity. If that cannot be assured, you still need to follow another algorithm, like the one described above. So it is a choice of minimizing the number of tree manipulations at the cost of dealing with more (special) cases.