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

1 package weiss.nonstandard;
2
3 // RedBlackTree class
4 //
5 // CONSTRUCTION: with no parameters
6 //
7 // ******************PUBLIC OPERATIONS*********************
8 // Same as BinarySearchTree; omitted for brevity
9 // ******************ERRORS********************************
10 // Exceptions are thrown by insert if warranted and remove.
11
12 public class RedBlackTree<AnyType extends Comparable<? super AnyType>>
13 {
14 public RedBlackTree( )
15 { /* Figure 19.44 */ }
16
17 public void insert( AnyType item )
18 { /* Figure 19.47 */ }
19 public void remove( AnyType x )
20 { /* Not implemented */ }
21
22 public AnyType findMin( )
23 { /* See online code */ }
24 public AnyType findMax( )
25 { /* Similar to findMin */ }
26 public AnyType find( AnyType x )
27 { /* Figure 19.46 */ }
28
29 public void makeEmpty( )
30 { header.right = nullNode; }
31 public boolean isEmpty( )
32 { return header.right == nullNode; }
33 public void printTree( )
34 { printTree( header.right ); }
35
36 private void printTree( RedBlackNode<AnyType> t )
37 { /* Figure 19.45 */ }
38 private final int compare( AnyType item, RedBlackNode<AnyType> t )
39 { /* Figure 19.47 */ }
40 private void handleReorient( AnyType item )
41 { /* Figure 19.48 */ }
42 private RedBlackNode<AnyType>
43 rotate( AnyType item, RedBlackNode<AnyType> parent )
44 { /* Figure 19.49 */ }
45
46 private static <AnyType>
47 RedBlackNode<AnyType> rotateWithLeftChild( RedBlackNode<AnyType> k2 )
48 { /* Implementation is as usual; see online code */ }
49 private static <AnyType>
50 RedBlackNode<AnyType> rotateWithRightChild( RedBlackNode<AnyType> k1 )
51 { /* Implementation is as usual; see online code */ }

figure 19.43a
The RedBlackTree class skeleton ( continues )