Java Reference
In-Depth Information
figure 19.64b
The class skeleton for
AA-trees ( continues )
24
25 public void remove( AnyType x )
26 { deletedNode = nullNode; root = remove( x, root ); }
27 public AnyType findMin( )
28 { /* Implementation is as usual; see online code */ }
29 public AnyType findMax( )
30 { /* Implementation is as usual; see online code */ }
31 public AnyType find( AnyType x )
32 { /* Implementation is as usual; see online code */ }
33 public void makeEmpty( )
34 { root = nullNode; }
35 public boolean isEmpty( )
36 { return root == nullNode; }
37
38 private AANode<AnyType> insert( AnyType x, AANode<AnyType> t )
39 { /* Figure 19.65 */ }
40 private AANode<AnyType> remove( AnyType x, AANode<AnyType> t )
41 { /* Figure 19.67 */ }
42 private AANode<AnyType> skew( AANode<AnyType> t )
43 { /* Figure 19.66 */ }
44 private AANode<AnyType> split( AANode<AnyType> t )
45 { /* Figure 19.66 */ }
46
47 private static <AnyType>
48 AANode<AnyType> rotateWithLeftChild( AANode<AnyType> k2 )
49 { /* Implementation is as usual; see online code */ }
50 private static <AnyType>
51 AANode<AnyType> rotateWithRightChild( AANode<AnyType> k1 )
52 { /* Implementation is as usual; see online code */ }
53
54 private static class AANode<AnyType>
55 {
56 // Constructors
57
AANode( AnyType theElement )
{
58
element = theElement;
59
left = right = nullNode;
60
level = 1;
61
62 }
63
64 AnyType element; // The data in the node
65 AANode<AnyType> left; // Left child
66 AANode<AnyType> right; // Right child
67 int level; // Level
68 }
69
70 private AANode<AnyType> root;
71 private AANode<AnyType> nullNode;
72
73 private AANode<AnyType> deletedNode;
74 private AANode<AnyType> lastNode;
75 }
Search WWH ::




Custom Search