AVL TREES - Introduction to Java Programming: Comprehensive Version - page 980

Need LL rotation
at node 25

25 25 20 20

20 20 5 25 5 25

5 34

(a) Insert 25, 20 (b) Insert 5 (c) Balanced (d) Insert 34

20 20 20

Need RR rotation
at node 25

RL rotation at
node 20

5 25 5 34 5 34

34 25 50 25 50

50

30

(e) Insert 50 (f) Balanced (g) Insert 30

25 25 25

LR rotation at
node 20

20 34 20 34 10 34

5 30 50 5 30 50 5 20 30 50

10

(h) Balanced (i) Insert 10 (j) Balanced

F IGURE 26.10

The tree evolves as new elements are inserted.

Figure 26.11 shows how the tree evolves as elements are deleted. After deleting 34 , 30 ,
and 50 , the tree is as shown in Figure 26.11b. The tree is not balanced. Perform an LL rotation
to result in an AVL tree, as shown in Figure 26.11c.
After deleting 5 , the tree is as shown in Figure 26.11d. The tree is not balanced. Perform
an RL rotation to result in an AVL tree, as shown in Figure 26.11e.

26.19

✓ ✓

Show the change of an AVL tree when inserting 1 , 2 , 3 , 4 , 10 , 9 , 7 , 5 , 8 , 6 into the
tree, in this order.

Check

Point

26.20

For the tree built in the preceding question, show its change after 1 , 2 , 3 , 4 , 10 , 9 , 7 ,
5 , 8 , 6 are deleted from the tree in this order.

26.21

Can you traverse the elements in an AVL tree using a foreach loop?