Data Structures with Generic Types in Java/

...

/

Removal from B-Tree

Removal from B-Tree

Learn about the remove() operation in B-tree.

We'll cover the following...

The remove(x) operation in a BTree is, again, most easily implemented as a recursive method. Although the recursive implementation of remove(x) spreads the complexity across several methods.

Visual demonstration of remove

The overall process, which is illustrated in the below illustration, is fairly straightforward.

By shuffling keys around, removal is reduced to the problem of removing a value, x', from some leaf, u. Removing x' may leave u with less than B−1B − 1 keys; this situation is called an underflow.

When an underflow occurs, u either borrows keys from, or is merged with, one of its siblings. If u is merged with a sibling, then u’s parent will now have one less child and one less key, which can cause u’s parent to underflow; this is again corrected by borrowing or merging, but merging may cause u’s grandparent to underflow. This process works its way back up to the root until there is no more underflow or until the root has its last two children merged into a single child. When the latter case occurs, the root is removed and its lone child becomes the new root.

Next, we delve into the details of how each of these steps is implemented. The first job of the remove(x) method is to find the element x that should be removed. If x is found in a leaf, then x is removed from this leaf. Otherwise, if x is found at u.keys[i] for some internal node, u, then the algorithm removes the smallest value, x', in the subtree rooted at u.children[i + 1]. The value x' is the smallest value stored in the BTree that is greater than x. The value of x' is then used to replace x in u.keys[i].

The remove(x) operation in a BTree is shown in the illustration below. To remove the value x = 10 we replace it with the value x' = 11 and remove 11 from the leaf that contains it.

Press + to interact
The remove(x) operation in a BTree
The remove(x) operation in a BTree

The removeRecursive(x,ui) method is a recursive implementation of the preceding algorithm:

Press + to interact
boolean removeRecursive(T x, int ui) {

  if (ui < 0) return false; // didn’t find it

  Node u = bs.readBlock(ui);

  int i = findIt(u.keys, x);

  if (i < 0) { // found it

    i = -(i + 1);

    if (u.isLeaf()) {

      u.remove(i);

    } else {

      u.keys[i] = removeSmallest(u.children[i + 1]);

      checkUnderflow(u, i + 1);

    }

    return true;

  } else if (removeRecursive(x, u.children[i])) {

    checkUnderflow(u, i);

    return true;

  }

  return false;

}

T removeSmallest(int ui) {

  Node u = bs.readBlock(ui);

  if (u.isLeaf())

    return u.remove(0);

  T y = removeSmallest(u.children[0]);

  checkUnderflow(u, 0);

  return y;

}

Note that, after recursively removing the value x from the ithi^{th} child of u, removeRecursive(x, ui) needs to ensure that this child still has at least B−1B − 1 keys. In the preceding code, this is done using a method called checkUnderflow(x, i), which checks for and corrects an underflow in the ithi^{th} child of u. Let w be the ...