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

The pseudocode to implement the case 2 double rotation is compact and
is shown in Figure 19.32. The mirror-image pseudocode for case 3 is shown
in Figure 19.33.

19.4.4 summary of avl insertion

Here is a brief summary how an AVL insertion is implemented. A recursive
algorithm turns out to be the simplest method of implementing an AVL inser-
tion. To insert a new node with key X in an AVL tree T, we recursively insert it
in the appropriate subtree of T (denoted T LR ). If the height of T LR does not
change, we are done. Otherwise, if a height imbalance appears in T , we do the
appropriate single or double rotation (rooted at T ), depending on X and the
keys in T and T LR , and then we are done (because the old height is the same as
the postrotation height). This recursive description is best described as a
casual implementation. For instance, at each node we compare the subtree's
heights. In general, storing the result of the comparison in the node is more
efficient than maintaining the height information. This approach avoids the
repetitive calculation of balance factors. Furthermore, recursion incurs sub-
stantially more overhead than does an iterative version. The reason is that, in
effect, we go down the tree and completely back up instead of stopping as
soon as a rotation has been performed. Consequently, in practice, other bal-
anced search tree schemes are used.

A casual AVL
implementation is
not excessively
complex, but it is
not efficient. Better
balanced search
trees have since
been discovered, so
implementing an
AVL tree is not
worthwhile.

1 /**
2 * Double rotate binary tree node: first left child
3 * with its right child; then node k3 with new left child.
4 * For AVL trees, this is a double rotation for case 2.
5 */
6 static BinaryNode doubleRotateWithLeftChild( BinaryNode k3 )
7 {
8 k3.left = rotateWithRightChild( k3.left );
9 return rotateWithLeftChild( k3 );
10 }

figure 19.32
Pseudocode for a
double rotation
(case 2)

1 /**
2 * Double rotate binary tree node: first right child
3 * with its left child; then node k1 with new right child.
4 * For AVL trees, this is a double rotation for case 3.
5 */
6 static BinaryNode doubleRotateWithRightChild( BinaryNode k1 )
7 {
8 k1.right = rotateWithLeftChild( k1.right );
9 return rotateWithRightChild( k1 );
10 }

figure 19.33
Pseudocode for a
double rotation
(case 3)