Binary search trees - Data Structures and Problem Solving Using Java - page 742

1 /**
2 * This method is not part of standard Java.
3 * Like contains, it checks if x is in the set.
4 * If it is, it returns the reference to the matching
5 * object; otherwise it returns null.
6 * @param x the object to search for.
7 * @return if contains(x) is false, the return value is null;
8 * otherwise, the return value is the object that causes
9 * contains(x) to return true.
10 */
11 public AnyType getMatch( AnyType x )
12 {
13 AANode<AnyType> p = find( x );
14 if( p == null )
15 return null;
16 else
17 return p.element;
18 }
19
20 /**
21 * Find an item in the tree.
22 * @param x the item to search for.
23 * @return the matching item or null if not found.
24 */
25 private AANode<AnyType> find( AnyType x )
26 {
27 AANode<AnyType> current = root;
28 nullNode.element = x;
29
30 for( ; ; )
31 {
32

figure 19.70
Search methods for
TreeSet

int result = compare( x, current.element );

33
34 if( result < 0 )
35 current = current.left;
36 else if( result > 0 )
37 current = current.right;
38 else if( current != nullNode )
39 return current;
40 else
41 return null;
42 }
43 }
44
45 private int compare( AnyType lhs, AnyType rhs )

{

46

if( cmp == null ) 47

return ((Comparable) lhs).compareTo( rhs );

48

else 49

return cmp.compare( lhs, rhs );

50

} 51