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

figure 19.23
Single rotation to fix
case 1

k 2 k 1

k 1 k 2

C

B A B C

A

(a) Before rotation (b) After rotation

in the original tree, can be placed as k 2 's left child in the new tree and satisfy
all the ordering requirements.

This work requires only the few child link changes shown as pseudocode
in Figure 19.24 and results in another binary tree that is an AVL tree. This out-
come occurs because A moves up one level, B stays at the same level, and C
moves down one level. Thus k 1 and k 2 not only satisfy the AVL requirements,
but they also have subtrees that are the same height. Furthermore, the new
height of the entire subtree is exactly the same as the height of the original
subtree before the insertion that caused A to grow. Thus no further updating of
the heights on the path to the root is needed, and consequently, no further
rotations are needed . We use this single rotation often in other balanced tree
algorithms in this chapter.
Figure 19.25(a) shows that after the insertion of 1 into an AVL tree, node 8
becomes unbalanced. This is clearly a case 1 problem because 1 is in 8's left-
left subtree. Thus we do a single rotation between 8 and 4, thereby obtaining
the tree shown in Figure 19.25(b). As mentioned earlier in this section, case 4
represents a symmetric case. The required rotation is shown in Figure 19.26,

One rotation
suffices to fix cases
1 and 4 in an AVL
tree.

1 /**
2 * Rotate binary tree node with left child.
3 * For AVL trees, this is a single rotation for case 1.
4 */
5 static BinaryNode rotateWithLeftChild( BinaryNode k2 )
6 {
7 BinaryNode k1 = k2.left;
8 k2.left = k1.right;
9 k1.right = k2;
10 return k1;
11 }

figure 19.24
Pseudocode for a
single rotation
(case 1)