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