data structure and algorithm for smiu student

data structure and algorithm for smiu studentdata structure and algorithm for smiu studentdata structure and algorithm for smiu studentdata structure and algorithm for smiu studentdata structure and algorithm for smiu studentdata structure and algorithm for smiu studentdata structure and algorithm for smiu studentdata structure and algorithm for smiu studentdata structure and algorithm for smiu student

1. 1
Data Structures
Lecture 21

2. 2
AVL Tree Building Example
Insert(3) single left rotation
1
2
3
-2

3. 3
AVL Tree Building Example
Insert(3)
1
2
3

4. 4
AVL Tree Building Example
Insert(4)
1
2
3
4

5. 5
AVL Tree Building Example
Insert(5)
1
2
3
4
5
-2

6. 6
AVL Tree Building Example
Insert(5)
1
2
3
4
5

7. 7
AVL Tree Building Example
Insert(6)
1
2
3
4
5
6
-2

8. 8
AVL Tree Building Example
Insert(6)
1
2
3
4
5
6

9. 9
AVL Tree Building Example
Insert(7)
1
2
3
4
5
6
7
-2

10. 10
AVL Tree Building Example
Insert(7)
1
2
3
4
5
6
7

11. 11
AVL Tree Building Example
1
2
3
4
5
6
7
16
Insert(16)

12. 12
AVL Tree Building Example
Insert(15)
1
2
3
4
5
6
7
16
15
-2

13. 13
AVL Tree Building Example
Insert(15)
1
2
3
4
5
6
7
16
15
-2

14. 14
Cases for Rotation
Single rotation does not seem to restore
the balance.
The problem is the node 15 is in an inner
subtree that is too deep.