avl-tree-animation and trversals and balancing

AVL Tree animation

1. AVL Tree Example:
• Insert 14, 17, 11, 7, 53, 4, 13 into an empty AVL tree
14
1711
7 53
4

2. AVL Tree Example:
• Insert 14, 17, 11, 7, 53, 4, 13 into an empty AVL tree
14
177
4 5311
13

3. AVL Tree Example:
• Now insert 12
14
177
4 5311
13
12

4. AVL Tree Example:
• Now insert 12
14
177
4 5311
12
13

5. AVL Tree Example:
• Now the AVL tree is balanced.
14
177
4 5312
1311

6. AVL Tree Example:
• Now insert 8
14
177
4 5312
1311
8

7. AVL Tree Example:
• Now insert 8
14
177
4 5311
128
13

8. AVL Tree Example:
• Now the AVL tree is balanced.
14
17
7
4
53
11
12
8 13

9. AVL Tree Example:
• Now remove 53
14
17
7
4
53
11
12
8 13

10. AVL Tree Example:
• Now remove 53, unbalanced
14
17
7
4
11
12
8 13

11. AVL Tree Example:
• Balanced! Remove 11
14
17
7
4
11
128
13

12. AVL Tree Example:
• Remove 11, replace it with the largest in its left branch
14
17
7
4
8
12
13

13. AVL Tree Example:
• Remove 8, unbalanced
14
17
4
7
12
13

14. AVL Tree Example:
• Remove 8, unbalanced
14
17
4
7
12
13

15. AVL Tree Example:
• Balanced!!
14
17
4
7
12
13

16. In Class Exercises
•Build an AVL tree with the following values:
15, 20, 24, 10, 13, 7, 30, 36, 25

17. 15
15, 20, 24, 10, 13, 7, 30, 36, 25
20
24
15
20
24
10
13
15
20
24
13
10
13
20
24
1510

18. 13
20
24
1510
15, 20, 24, 10, 13, 7, 30, 36, 25
7
13
20
2415
10
7
30
3613
20
3015
10
7
3624

19. 13
20
3015
10
7
3624
15, 20, 24, 10, 13, 7, 30, 36, 25
25
13
20
30
15
10
7
36
24
25
13
24
36
20
10
7
25
30
15

20. Remove 24 and 20 from the AVL tree.
13
24
36
20
10
7
25
30
15
13
20
36
15
10
7
25
30
13
15
36
10
7
25
30
13
30
36
10
7
25
15