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.
Getting Started
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.
 
 
Search WWH ::




Custom Search