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

figure 19.63
When 1 is deleted, all
nodes become level 1,
thereby introducing
horizontal left links.

2 5

1 3 4 6 7

children, and those children's horizontal right children. Figure 19.63 shows
the simplest possible scenario.

After node 1 has been removed, node 2 and thus node 5 become level-1
nodes. First, we must fix the left horizontal link that is now introduced
between nodes 5 and 3. Doing so essentially requires two rotations: one
between nodes 5 and 3 and then one between nodes 5 and 4. In this case, the
current node T is not involved. However, if a deletion came from the right
side, T 's left node could suddenly become horizontal; that would require a
similar double rotation (starting at T ). To avoid testing all these cases, we
merely call skew three times. Once we have done that, two calls to split suf-
fice to rearrange the horizontal edges.

After a recursive
removal, three
skew s and two
split s guarantee
rebalancing.

The implementa-
tion is relatively
simple (compared
to those of the
red-black tree).

19.6.3 java implementation

The class skeleton for the AA-tree is shown in Figure 19.64 and includes a
nested node class. Much of it duplicates previous tree code. Again, we use a

1 package weiss.nonstandard;
2
3 // AATree class
4 //
5 // CONSTRUCTION: with no initializer
6 //
7 // ******************PUBLIC OPERATIONS*********************
8 // Same as BinarySearchTree; omitted for brevity
9 // ******************ERRORS********************************
10 // Exceptions are thrown by insert and remove if warranted
11
12 public class AATree<AnyType extends Comparable<? super AnyType>>
13 {
14 public AATree( )
15 {
16

Figure 19.64a
The class skeleton for
AA-trees ( continues )

nullNode = new AANode<AnyType>( null, null, null );

nullNode.left = nullNode.right = nullNode; 17

nullNode.level = 0; 18

root = nullNode; 19

20 }
21
22 public void insert( AnyType x )
23 { root = insert( x, root ); }