Java Reference
In-Depth Information
place
k
2
as the new root. Doing so forces
k
1
to be
k
2
's left child and
k
3
to be
k
2
's right child. It also determines the resulting locations of the four subtrees,
and the resulting tree satisfies the AVL property. Also, as was the case with the
single rotation, it restores the height to the height before the insertion, thus
guaranteeing that all rebalancing and height updating are complete.
As an example, Figure 19.30(a) shows the result of inserting 5 into an
AVL tree. A height imbalance is caused at node 8, resulting in a case 2 prob-
lem. We perform a double rotation at that node, thereby producing the tree
shown in Figure 19.30(b).
Figure 19.31 shows that the symmetric case 3 can also be fixed by a dou-
ble rotation. Finally, note that, although a double rotation appears complex, it
turns out to be equivalent to the following sequence:
A
double rotation
is
equivalent to two
single rotations.
A rotation between
X
's child and grandchild
n
A rotation between
X
and its new child
n
figure 19.30
Double rotation fixes
AVL tree after the
insertion of 5.
12
12
k
3
k
2
16
16
8
6
k
1
k
1
k
3
D
14
14
4
10
4
8
k
2
A
A
B
C
D
2
2
6
5
10
BC
5
(a) Before rotation
(b) After rotation
figure 19.31
Right-Left double
rotation to fix case 3.
k
1
k
2
k
1
k
3
k
3
k
2
A
B
C
D
A
D
B
C
(a) Before rotation
(b) After rotation
Search WWH ::
Custom Search