next up previous contents index Search
Next: 0.2.3.2 Source Code Up: 0.2.3 Binary Search Trees Previous: 0.2.3 Binary Search Trees

0.2.3.1 Inserting and Deleting Nodes

To create a BST begin with a null pointer to the non-existent root node. Insert data values by examining the value of the root node and moving left or right down the tree until you have reached the proper insertion point. If there is no root node, (i.e. the tree is empty) the very first node inserted becomes the new root node. Ideally this first value should be the median value in the data set as this will cause the number of nodes on each side of the root to be equal.

If, however, the root node turns out to be the lowest or highest item in the data set a degenerate tree will result. A careful programmer should take steps to ensure that the root of a BST is not an extreme value. This can be accomplished by examining the values in the data set before building the tree. Robust execution time can be maintained by examining only two or three items and selecting the larger of two or the middle of three as the root.

To delete a node from a BST you must not only find the node in the tree by traversing in the usual manner, but also ensure that the BST retains the ``binary search tree property.'' If the node to be deleted, node d, has no children, it can be deleted outright. If node d has only one child, promote the child and use it to overwrite the contents of node d. If node d has two children, however, things get a bit tricky.

Deleting a node, d, that has two children requires that we find the node, e, in the tree with the next higher or lower value. To do so, traverse in one direction to one of d's children and then continually traverse in the opposite direction until you can go no further. For example, traverse to d's left child and then continue to traverse to right children as far as possible. Swap the last node with d then delete d. In essence, make d's value that of the last node and then delete the last node.

Scott Gasch
1999-07-09