Java Reference
In-Depth Information
A left rotation about
G
restores the balance of the tree, as you can see in Figure 27-7d. Note that
G
first rotates above
C
and then above
N
.
FIGURE 27-7
Before and after an addition to an AVL subtree that requires
both a right rotation and a left rotation to maintain its balance
(a) Before addition
(b) After addition
N
N
C
C
G
G
h
h
+ 1
T
1
T
1
T
2
T
3
T
4
T
2
T
4
T
3
(c) After right rotation
(d) After left rotation
N
G
G
N
C
C
h
+ 1
h
T
1
T
2
T
2
T
3
T
4
T
1
T
3
T
4
The following algorithm performs the right-left double rotation illustrated in Figure 27-7:
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)
The right rotation transforms the tree in Figure 27-7b into the one in Figure 27-7c. The left rotation
then transforms Figure 27-7c to Figure 27-7d.
Question 5
Using the notation of Figure 27-7, label nodes
N
,
C
, and
G
, and subtrees
T
1
,
T
2
,
T
3
,
and
T
4
in Figure 27-6.
27.5
Left-right double rotations.
Now we add 55, 10, and 40 to the tree in Figure 27-6c to get the tree
in Figure 27-8a. As long as we add 55 first, these additions maintain the tree's balance without rota-
tions. After we add 35, as Figure 27-8b shows, the tree is unbalanced at the node containing 50. To
restore the balance, we perform a left rotation about the node containing 40—so 40 rotates above
20—to get the tree in Figure 27-8c. Then we perform a right rotation about the node containing
40—so 40 rotates above 50—to get the balanced tree in Figure 27-8d.