Balanced Search Trees - Data Structures and Abstractions with Java - page 700

public AVLTree()
{

super ();
} // end default constructor

public AVLTree(T rootEntry)
{

super (rootEntry);
} // end constructor

< Implementations of add and remove are here. A definition of add appears in Segment 27.12
of this chapter. Other methods in SearchTreeInterface are inherited. >
. . .
< Implementations of private methods to rebalance the tree using rotations are here. >
. . .
} // end AVLTree

27.9

Rotations. As we discussed earlier, an AVL tree uses rotations to maintain its balance following the
addition or removal of a node. The methods that perform these rotations closely follow the pseudo-
code given in the previous segments.
For example, consider the algorithm for a single right rotation, as given in Segment 27.2:
Algorithm rotateRight(nodeN)
// Corrects an imbalance at a given node nodeN due to an addition
// in the left subtree of nodeN 's left child.

nodeC = left child of nodeN
Set nodeN 's left child to nodeC 's right child
Set nodeC 's right child to nodeN
return nodeC

The following method implements this pseudocode as a private method of the class AVLTree :

// Corrects an imbalance at the node closest to a structural
// change in the left subtree of the node's left child.
// nodeN is a node, closest to the newly added leaf, at which
// an imbalance occurs and that has a left child.
private BinaryNodeInterface<T> rotateRight(BinaryNodeInterface<T> nodeN)
{

BinaryNodeInterface<T> nodeC = nodeN.getLeftChild();
nodeN.setLeftChild(nodeC.getRightChild());
nodeC.setRightChild(nodeN);
return nodeC;
} // end rotateRight
The method rotateLeft has a similar implementation and is left as an exercise.
Since a double rotation is equivalent to two single rotations, the methods that perform double
rotations each call the methods that perform single rotations. For example, the algorithm for a right-
left double rotation, as it appeared in Segment 27.4, is
Algorithm rotateRightLeft(nodeN)
// Corrects an imbalance at a given node nodeN due to an addition
// in the left subtree of nodeN 's right child.

nodeC = right child of nodeN
Set nodeN 's right child to the node returned by rotateRight(nodeC)
return rotateLeft(nodeN)