Java Reference
In-Depth Information
120
37
42
24
42
7
42
40
42
7
32
2
32
2
120
24
37
40
(A)
(B)
Figure5.13
Two Binary Search Trees for a collection of values. Tree (a) results
if values are inserted in the order 37, 24, 42, 7, 2, 40, 42, 32, 120. Tree (b) results
if the same values are inserted in the order 120, 42, 42, 7, 2, 32, 37, 24, 40.
key value K is found, or we reach a leaf node. If we reach a leaf node without
encountering K, then no record exists in the BST whose key value is K.
Example5.5
Consider searching for the node with key value 32 in the
tree of Figure 5.13(a). Because 32 is less than the root value of 37, the
search proceeds to the left subtree. Because 32 is greater than 24, we search
in 24's right subtree. At this point the node containing 32 is found. If
the search value were 35, the same path would be followed to the node
containing 32. Because this node has no children, we know that 35 is not
in the BST.
Notice that in Figure 5.14, public member function
find
calls private member
function
findhelp
. Method
find
takes the search key as an explicit parameter
and its BST as an implicit parameter, and returns the record that matches the key.
However, the find operation is most easily implemented as a recursive function
whose parameters are the root of a subtree and the search key. Member
findhelp
has the desired form for this recursive subroutine and is implemented as follows.
privateEfindhelp(BSTNode<Key,E>rt,Keyk){
if(rt==null)returnnull;
if(rt.key().compareTo(k)>0)
returnfindhelp(rt.left(),k);
elseif(rt.key().compareTo(k)==0)returnrt.element();
elsereturnfindhelp(rt.right(),k);
}
Once the desired record is found, it is passed through return values up the chain of
recursive calls. If a suitable record is not found,
null
is returned.
