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

Implementation

Insertion in a B-tree is a two-pass process. The first pass moves down the tree from the root in order to locate the leaf in which the insertion is to begin. This part of the algorithm is quite similar to the Find method given in Program gif. The second pass moves from the bottom of the tree back up to the root, splitting nodes and inserting them further up the tree as needed. Program gif gives the code for the first (downward) pass (Insert method) and the Program gif gives the code for the second (upward) pass (InsertPair method).

   program21967
Program: BTree class Insert method.

In the implementation shown, the downward pass starts at the root node and descends the tree until it arrives at an external node. If the external node has no parent, it must be the root and, therefore, the tree is empty. In this case, the root becomes an internal node containing a single key and two empty subtrees (lines 11-13). Otherwise, we have arrived at an external node in a non-empty tree and the second pass begins by calling InsertPair to insert the pair tex2html_wrap_inline64843 in the parent.

The upward pass of the insertion algorithm is done by the recursive InsertPair method shown in Program gif. The InsertPair method takes two arguments. The first, object, is a ComparableObject and the second, child, is a BTree. It is assumed that all the keys in child are strictly greater than object.

   program21986
Program: BTree class InsertPair method.

The InsertPair method calls FindIndex to determine the position in the array of keys at which pair (object,child) should be inserted (line 8). If this node is full (line 9), the InsertKey is called to insert the given key at the specified position in the key array (line 11) and InsertSubtree is called to insert the given tree at the specified position in the subtree array (line 12).

In the event that the node is full, the InsertKey method returns the key which falls off the right end of the array. This is assigned to extraKey (line 17). Similarly, the InsertSubtree method returns the tree which falls of the right end of the array. This is assigned to extraTree (line 19).

The node has now overflowed and it is necessary to balance the B-tree. If the node overflows and it is the root (line 20), then two new B-trees, left and right are created (lines 22-23). The first tex2html_wrap_inline64787 keys and tex2html_wrap_inline64759 subtrees of the given node are moved to the left tree by the AttachLeftHalfOf method (line 24); and the last tex2html_wrap_inline64945 keys and tex2html_wrap_inline64947 subtrees of the given node are moved to the right tree by the AttachRightHalfOf method (line 25). Then, the pair (extraKey,extraTree) is inserted into the right tree (line 26).

The left-over key is the one in the middle of the array, i.e., tex2html_wrap_inline64883. Finally, the root node is modified so that it contains the two new subtrees and the single left-over key (lines 27-30).

If the node overflows and it is not the root, then one new B-tree is created, right (line 35). The last tex2html_wrap_inline64945 keys and tex2html_wrap_inline64947 subtrees of the given node are moved to the left tree by the AttachRightHalfOf method (line 36) and the pair (extraKey,extraTree) is inserted in the right tree (line 37). The first tex2html_wrap_inline64787 keys and tex2html_wrap_inline64759 subtrees of the given node remain attached to it.

Finally, the InsertPair method calls itself recursively to insert the left-over key, tex2html_wrap_inline64883, and the new B-tree, right, into the parent of this (line 38). This is the place where the parent field is needed!


next up previous contents index

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