Binary Trees - Building Java Programs: A Back to Basics Approach - page 1017

1
2
3
...
We refer to this as a degenerate tree . It's technically still a tree, but it's not a very
good tree because it makes no use of the two branching possibilities. This is really a
linked list turned on its side. You can get similar degenerate trees if the values are
inserted in decreasing order, which produces a tree that expands indefinitely in the
left direction.
If the values are inserted into a binary search tree in a random order, then the odds
of getting a degenerate tree are fairly low. If you take a more advanced course in data
structures, you will study techniques for ensuring that the tree is balanced. For exam-
ple, the TreeMap and TreeSet structures in the Java class libraries are implemented
as what are called red/black trees to guarantee that the resulting binary search tree is
balanced.
Let's set aside the issue of degenerate trees and think about the case for random-
ized data or for binary search trees that guarantee balance. One important property of
the binary search tree is that each insertion into the tree requires you to descend from
level to level until you find an open spot to insert the value. Thus, insertion into a bal-
anced binary search tree is an O(log N ) operation. Similarly, finding a value in a bal-
anced binary search tree involves descending from level to level, so it also is an
O(log N ) operation. To search for a value in a normal binary tree, you would have to
search the entire tree. Although we haven't shown the solution here, we'll mention
that removing a value from a balanced binary search tree can also be accomplished as
an O(log N ) operation.
The binary search tree, then, offers insertion, search, and removal all in O(log N )
time. That means that if you are working with a trillion values, for example, you
can add a new value, search for a value, or remove a value, all within around 40 steps.
That makes the binary search tree a very efficient structure to use for these operations.
17.5 SearchTree<E>
In the previous section, we developed code for a binary search tree of integers. You
might want to build other kinds of binary search trees with different kinds of data and
you wouldn't want to make many copies of essentially the same code (one for inte-
gers, one for strings, etc). Instead, you want to write the code in a more generic way.
We want to be able to build a search tree for any class that implements the
Comparable interface. We want a class that we could call SearchTree<E> (for some