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

26 public void remove( AnyType x )
27 { root = remove( x, root ); }
28 public void removeMin( )
29 { root = removeMin( root ); }
30 public AnyType findMin( )
31 { return elementAt( findMin( root ) ); }
32 public AnyType findMax( )
33 { return elementAt( findMax( root ) ); }
34 public AnyType find( AnyType x )
35 { return elementAt( find( x, root ) ); }
36 public void makeEmpty( )
37 { root = null; }
38 public boolean isEmpty( )
39 { return root == null; }
40
41 private AnyType elementAt( BinaryNode<AnyType> t )
42 { /* Figure 19.7 */ }
43 private BinaryNode<AnyType> find( AnyType x, BinaryNode<AnyType> t )
44 { /* Figure 19.8 */ }
45 protected BinaryNode<AnyType> findMin( BinaryNode<AnyType> t )
46 { /* Figure 19.9 */ }
47 private BinaryNode<AnyType> findMax( BinaryNode<AnyType> t )
48 { /* Figure 19.9 */ }
49 protected BinaryNode<AnyType> insert( AnyType x, BinaryNode<AnyType> t )
50 { /* Figure 19.10 */ }
51 protected BinaryNode<AnyType> removeMin( BinaryNode<AnyType> t )
52 { /* Figure 19.11 */ }
53 protected BinaryNode<AnyType> remove( AnyType x, BinaryNode<AnyType> t )
54 { /* Figure 19.12 */ }
55
56 protected BinaryNode<AnyType> root;
57 }
figure 19.6b
The BinarySearchTree class skeleton ( continued )
Next, we have several methods that operate on a node passed as a
parameter, a general technique that we used in Chapter 18. The idea is that
the publicly visible class routines call these hidden routines and pass root
as a parameter. These hidden routines do all the work. In a few places, we
use protected rather than private because we derive another class from
BinarySearchTree in Section 19.2.
The insert method adds x to the current tree by calling the hidden insert
with root as an additional parameter. This action fails if x is already in the
tree; in that case, a DuplicateItemException would be thrown. The findMin ,
findMax , and find operations return the minimum, maximum, or named item
(respectively) from the tree. If the item is not found because the tree is empty