Java Reference
In-Depth Information
figure 19.25
Single rotation fixes
an AVL tree after
insertion of 1.
12
12
k 2
k 1
4
8
16
16
k 1
k 2
C
A
4
10
14
2
8
14
C
AB
B
2
6
1
6
10
1
(a) Before rotation
(b) After rotation
and the pseudocode that implements it is shown in Figure 19.27. This rou-
tine, along with other rotations in this section, is replicated in various bal-
anced search trees later in this text. These rotation routines appear in the
online code for several balanced search tree implementations.
figure 19.26
Symmetric single
rotation to fix case 4
k 2
k 1
k 1
k 2
A
A
B
C
B
C
(a) After rotation
(b) Before rotation
1 /**
2 * Rotate binary tree node with right child.
3 * For AVL trees, this is a single rotation for case 4.
4 */
5 static BinaryNode rotateWithRightChild( BinaryNode k1 )
6 {
7 BinaryNode k2 = k1.right;
8 k1.right = k2.left;
9 k2.left = k1;
10 return k2;
11 }
figure 19.27
Pseudocode for a
single rotation
(case 4)
 
 
Search WWH ::




Custom Search