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

1 /**
2 * Skew primitive for AA-trees.
3 * @param t the node that roots the tree.
4 * @return the new root after the rotation.
5 */
6 private static <AnyType> AANode<AnyType> skew( AANode<AnyType> t )
7 {
8 if( t.left.level == t.level )
9 t = rotateWithLeftChild( t );
10 return t;
11 }
12
13 /**
14 * Split primitive for AA-trees.
15 * @param t the node that roots the tree.
16 * @return the new root after the rotation.
17 */
18 private static <AnyType> AANode<AnyType> split( AANode<AnyType> t )
19 {
20 if( t.right.right.level == t.level )
21 {
22 t = rotateWithRightChild( t );
23 t.level++;
24 }
25 return t;
26 }

figure 19.66
The skew and split procedures for the AATree class

plus one extra equality test at the bottom. lastNode points at the level-1
node at which this search terminates. Because we do not stop until we
reach the bottom, if the item is in the tree, lastNode will reference the
level-1 node that contains the replacement value and must be removed
from the tree.
After a given recursive call terminates, we are either at level 1 or we are
not. If we are at level 1, we can copy the node's value into the internal node
that is to be replaced; we can then bypass the level-1 node. Otherwise, we are
at a higher level, and we need to determine whether the balance condition has
been violated. If so, we restore the balance and then make three calls to skew
and two calls to split . As discussed previously, these actions guarantee that
the AA-tree properties will be restored.

The deletedNode
variable references
the node contain-
ing x (if x is found)
or nullNode if x is
not found. The
lastNode variable
references the
replacement node.
We use two-way
comparisons
instead of three-
way comparisons.