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.
Search WWH ::




Custom Search