AVL tree animation.ppt

Animation PPT about AVL Tree

1. Animation PPT
Insertion with balanced binary tree
Example with solution
Exercise Problem
Mrs.R.Sabitha,
Assistant Professor,
Department of Computer Science(SF)
V.V.Vanniaperumal College for Women,
Virudhunagar

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

18. 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

19. 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

20. 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

21. 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