Logo Data Structures and Algorithms with Object-Oriented Design Patterns in C++
next up previous contents index

Removing Items from a B-Tree

The procedure for removing items from a B-tree is similar to the algorithm for removing item from an AVL tree. I.e., once the item to be removed has be found, it is pushed down the tree to a leaf node where it can be easily deleted. When an item is deleted from a node it is possible that the number of keys remaining is less than tex2html_wrap_inline65656. In this case, balancing is necessary.

The procedure of balancing after deletion is like the balancing after insertion in that it progresses from the leaf node up the tree toward the root. Given a node T which has tex2html_wrap_inline65856 keys, there are four cases to consider.

In the first case, T is the root. If no keys remain, T becomes the empty tree. Otherwise, no balancing is needed because the root is permitted to have as few as two subtrees and one key. For the remaining cases T is not the root.

In the second case T has tex2html_wrap_inline65856 keys and it also has a sibling immediately on the left with at least tex2html_wrap_inline65628 keys. The tree can be balanced by doing an LL rotation   as shown in Figure gif. Notice that after the rotation, both siblings have at least tex2html_wrap_inline65656 keys. Furthermore, the heights of the siblings remain unchanged. Therefore, the resulting tree is a valid B-tree.

   figure22731
Figure: LL Rotation in a B-Tree

The third case is the left-right mirror of the second case. I.e., T has tex2html_wrap_inline65856 keys and it also has a sibling immediately on the right with a least tex2html_wrap_inline65628 keys. In this case, the tree can be balanced by doing an RR rotation  .

In the fourth and final case, T has tex2html_wrap_inline65856 keys, and its immediate sibling(s) have tex2html_wrap_inline65656 keys. In this case, the sibling(s) cannot give-up a key in a rotation because they already have the minimum number of keys. The solution is to merge  T with one of its siblings as shown in Figure gif.

   figure23218
Figure: Merging nodes in a B-Tree

The merged node contains tex2html_wrap_inline65856 keys from T, tex2html_wrap_inline65656 keys from the sibling, and one key from the parent (the key x in Figure gif). The resulting node contains tex2html_wrap_inline66046 keys altogether, which is M-2 if M is even and M-1 if M is odd. Either way, the resulting node contains no more than M-1 keys and is a valid B-tree node. Notice that in this case a key has been removed from the parent of T. Therefore, it may be necessary to balance the parent. Balancing the parent may necessitate balancing the grandparent, and so on, up the tree to the root.


next up previous contents index

Bruno Copyright © 1997 by Bruno R. Preiss, P.Eng. All rights reserved.