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