Java Reference
In-Depth Information
Figure 27-9 shows a left-right double rotation in general. It is a mirror image of the right-left
double rotation pictured in Figure 27-7. Both left-right and right-left double rotations cause node
G
to rotate first above node
C
and then above node
N
.
The following algorithm performs the left-right double rotation illustrated in Figure 27-9:
Algorithm
rotateLeftRight(nodeN)
//
Corrects an imbalance at a given node
nodeN
due to an addition
//
in the right subtree of
nodeN
's left child.
nodeC =
left child of
nodeN
Set
nodeN
's left child to the node returned by
rotateLeft(nodeC)
return
rotateRight(nodeN)
Question 6
Using the notation of Figure 27-9, label nodes
N
,
C
, and
G
, and subtrees
T
1
,
T
2
,
T
3
,
and
T
4
in Figure 27-8.
Note:
A double rotation is accomplished by performing two single rotations:
1.
A rotation about node
N
's grandchild
G
(its child's child)
2.
A rotation about node
N
's new child
We can imagine G rotating first above
N
's original child
C
and then above
N.
Note:
An imbalance at node
N
of an AVL tree can be corrected by a double rotation if
•
The addition occurred in the left subtree of
N
's right child (right-left rotation), or
•
The addition occurred in the right subtree of
N
's left child (left-right rotation)
27.6
Summary comments about rotation after an addition.
Following an addition to an AVL tree, a
temporary imbalance might occur. Let
N
be an unbalanced node that is closest to the new leaf.
Either a single or double rotation will restore the tree's balance. No other rotations are necessary.
To see this, remember that before the addition, the tree was balanced; after all, it is an AVL tree.
After an addition that causes a rotation, the tree has the same height as it did before the addition.
Therefore, no node above
N
can be unbalanced now if it was balanced before the addition. More-
over, the four rotations cover the only four possibilities for the cause of the imbalance at node
N
:
•
The addition occurred in the left subtree of
N
's left child (right rotation)
•
The addition occurred in the right subtree of
N
's left child (left-right rotation)
•
The addition occurred in the left subtree of
N
's right child (right-left rotation)
•
The addition occurred in the right subtree of
N
's right child (left rotation)
Removing an entry from a binary search tree results in the removal of a node, but not necessar-
ily the node that contained the entry. Thus, removing an entry from an AVL tree can lead to a tem-
porary imbalance. We restore the tree's balance by using single or double rotations as described
previously for addition. We leave the details for you to develop in Project 1.
Note:
One single or double rotation during the addition of an entry will restore the balance
of an AVL tree.
