Java Reference
In-Depth Information
FIGURE 23-18
A binary search tree of names
Jared
Brittany
Megan
Brett
Jim
Whitney
Doug
23.28
The configuration of a binary search tree is not unique. That is, we can form several different
binary search trees from the same set of data. For example, Figure 23-19 shows two binary search
trees containing the same names that are in Figure 23-18; other binary search trees are possible.
Question 14
How many different binary search trees can you form from the strings
a
,
b
,
and
c
?
Question 15
What are the heights of the shortest and tallest trees that you formed in
Question 14?
FIGURE 23-19
Two binary search trees containing the same data as the tree in
Figure 23-18
(a)
(b)
Megan
Brett
Whitney
Doug
Brittany
Brittany
Jared
Doug
Jared
Jim
Brett
Jim
Megan
Whitney
23.29
Searching a binary search tree.
The organization of the nodes in a binary search tree enables us to
search the tree for a particular data object, given its search key. For example, suppose that we
search the tree in Figure 23-18 for the string
Jim
. Beginning at the root of the tree, we compare
Jim
with
Jared
. Since the string
Jim
is greater than the string
Jared
, we search the right subtree of the
root. Comparing
Jim
to
Megan
, we find that
Jim
is less than
Megan
. We search
Megan
's left subtree
next and find
Jim
.
