Java Reference
In-Depth Information
Objectives
After studying this chapter, you should be able to
•
Decide whether a binary tree is a binary search tree
•
Locate a given entry in a binary search tree using the fewest comparisons
•
Traverse the entries in a binary search tree in sorted order
•
Add a new entry to a binary search tree
•
Remove an entry from a binary search tree
•
Describe the efficiency of operations on a binary search tree
•
Use a binary search tree to implement the ADT dictionary
R
ecall from Chapter 23 that a search tree stores data in a way that facilitates searching. In particular,
we saw the binary search tree, which is both a binary tree and a search tree. The nature of a binary
search tree enables us to search it by using a simple recursive algorithm. This algorithm is similar in
spirit to a binary search of an array and can be just as efficient. However, the shape of a binary search
tree affects the efficiency of this algorithm. Since we can create several different binary search trees
from the same data, we want to pick the tree whose shape provides the most efficient search.
For a database that remains stable, a binary search tree provides a relatively simple way to
achieve an efficient search. Most databases, however, change to remain current. Thus, we must add
nodes to and remove nodes from the binary search tree. Unfortunately, these operations change the
shape of the tree, often making a search less efficient.
This chapter implements the binary search tree and, in doing so, describes the algorithms for
adding and removing entries. Chapter 27 looks at ways that a search tree can provide an efficient
search despite additions and removals.
25.1
A
binary search tree
is a binary tree whose nodes contain
Comparable
objects and are organized
as follows. For each node in the tree,
•
The data in a node is greater than the data in the node's left subtree
•
The data in a node is less than the data in the node's right subtree
Figure 25-1 shows the binary search tree that you saw in Chapter 23.
FIGURE 25-1
A binary search tree of names
Jared
Brittany
Megan
Brett
Doug
Jim
Whitney
Recall that a
Comparable
object belongs to a class that implements the interface
Comparable
.
We use the class's method
compareTo
to compare such objects. The basis for this comparison varies
from class to class, depending on the data fields
compareTo
examines.