|
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.
|
Search