Java Reference
In-Depth Information
FIGURE 27-8
(a) The AVL tree in Figure 27-6c after additions that maintain
its balance; (b) after an addition that destroys the balance;
(c) after a left rotation; (d) after a right rotation
(a) After adding 55, 10, and 40
(b) After adding 35
60
60
Imbalance at
this node
50
80
50
80
55
70
20
90
20
55
70
90
10
40
40
10
35
(c) After left rotation about 40
(d) After right rotation about 40
60
60
50
80
40
80
40
55
70
90
20
50
70
90
20
35
10
55
10
35
FIGURE 27-9
Before and after an addition to an AVL subtree that requires
both a left rotation and a right rotation to maintain its balance
(b) After addition
(a) Before addition
N
N
C
C
G
G
h
h
1
T
4
T
4
T
1
T
2
T
3
T
3
T
1
T
2
(d) After right rotation
(c) After left rotation
N
G
G
N
C
C
h
h
+ 1
T
3
T
4
T
3
T
1
T
2
T
4
T
1
T
2
