Java Reference
In-Depth Information
726
Figure 12
Removing a Node with Two Children
At the end of this section, you will find the source code for the
BinarySearchTree
class. It contains the
add
and
remove
methods that we just
described, as well as a
find
method that tests whether a value is present in a binary
search tree, and a
print
method that we will analyze in the following section.
Now that you have seen the implementation of this complex data structure, you may
well wonder whether it is any good. Like nodes in a list, nodes are allocated one at a
time. No existing elements need to be moved when a new element is inserted in the
tree; that is an advantage. How fast insertion is, however, depends on the shape of the
tree. If the tree is balancedȌthat is, if each node has approximately as many
descendants on the left as on the rightȌthen insertion is very fast, because about half
of the nodes are eliminated in each step. On the other hand, if the tree happens to be
