Trees - Data Structures and Abstractions with Java - page 586

To search for Laura , we would compare Laura with Jared , then with Megan , and then with
Jim . Since Laura is greater than Jim , we would search Jim 's right subtree. But this subtree is empty,
so we conclude that Laura does not occur in the tree.
We can express our search algorithm recursively: To search a binary search tree, we search one
of its two subtrees. The search ends when either we find the item we seek or we encounter an empty
subtree. We can formalize this search by writing the following pseudocode:

Algorithm bstSearch(binarySearchTree, desiredObject)
// Searches a binary search tree for a given object.
// Returns true if the object is found.

if ( binarySearchTree is empty)
return false
else if (desiredObject == object in the root of binarySearchTree)
return true
else if (desiredObject < object in the root of binarySearchTree)
return bstSearch( left subtree of binarySearchTree, desiredObject)
else
return bstSearch( right subtree of binarySearchTree, desiredObject)

This algorithm is somewhat like a binary search of an array. Here we search one of two subtrees; a
binary search searches one half of an array. You will see how to implement this algorithm in Chapter 25.
If you think that you could implement the ADT dictionary by using a binary search tree, you
would be right. Chapter 25 will show you how.

23.30

The efficiency of a search. The algorithm bstSearch examines nodes along a path through a
binary search tree, beginning at the tree's root. The path ends at either the node that contains the
desired object or some other node that is a leaf. In the previous segment, the search for Jim in
Figure 23-18 examined the three nodes containing Jared , Megan , and Jim . In general, the number
of comparisons that a successful search requires is the number of nodes along the path from the root
to the node that contains the desired item.
Searching for Jim in Figure 23-19a requires four comparisons; searching Figure 23-19b for
Jim requires five comparisons. Both trees in Figure 23-19 are taller than the tree in Figure 23-18.
As you can see, the height of a tree directly affects the length of the longest path from the root to a
leaf and hence affects the efficiency of a worst-case search. Thus, searching a binary search tree of
height h is O( h ).
Note that the tree in Figure 23-19b is as tall as a tree containing seven nodes can be. A search
of this tree has the performance of a sequential search of either a sorted array or a sorted linked
chain. Each of these searches has an efficiency of O( n ).
To make searching a binary search tree as efficient as possible, the tree must be as short as pos-
sible. The tree in Figure 23-18 is full and is the shortest possible binary search tree that we can form
with this data. As you will see in Chapter 25, inserting or deleting nodes can change the shape of a
binary search tree. Thus, such operations can decrease the time efficiency of a search. Chapter 27
will show you strategies for maintaining the search's efficiency.

Heaps

23.31

Definitions. A heap is a complete binary tree whose nodes contain Comparable objects and are
organized as follows. Each node contains an object that is no smaller (or no larger) than the objects
in its descendants. In a maxheap , the object in a node is greater than or equal to its descendant
objects. In a minheap , the relation is less than or equal to. Figure 23-20 gives an example of a max-
heap and a minheap. For simplicity, we use integers instead of objects in our illustrations.