AVL Trees in Data Structures: Lecture Insights
Data Structures
Lecture 5
Instructor: Ghazwan Abdulnabi Al-Ali
University of Basrah, Iraq
3
rd
Grade
College of Computer Science and Information Technology
Department of Computer Science
AVL Trees
Sibling
Internal
Ancestors
Subtree
AVL
•
balance factor = Left-Right.
1
6
2
11
5
8
AVL
•
balance factor = left-right.
3-1= +2
+2
1
6
2
11
5
8
AVL
•
balance factor = left-right.
2-1= +1
+2
+1
1
6
2
11
5
8
AVL
•
balance factor = left-right.
1-0= +1
+2
+1
+1
1
6
2
11
5
8
AVL
•
balance factor = left-right.
6
2
11
5
8
0-0= 0
+2
+1
+1
0
0
1
0
AVL (Single Rotation
)
Case
1
+ & +
Turn Right
+ 2
+ 1
+1
0
0
0
1
6
2
11
5
8
AVL (Single Rotation
)
Case
1
+ & +
Turn Right
8
2
5
+ 2
+ 1
+1
0
0
0
1
6
2
11
5
8
1
11
عائم
6
AVL (Single Rotation
)
Case
2
- & -
Turn Left
15
12
5
10
20
-1
0
0
- 1
30
0
- 2
AVL (Single Rotation
)
Case
2
- & -
Turn Left
15
12
5
10
20
-1
0
0
- 1
30
0
- 2
20
10
15
30
5
12
عائم
AVL (Double Rotation
)
Case
1
70
30
40
45
35
50
20
36
AVL (Double Rotation
)
Case
1
+ & -
1.
Turn Left
2.
Turn Right
70
40
45
0
35
-1
0
+ 3
0
+1
- 2
20
36
0
50
30
AVL (Double Rotation
)
Case
1
+ & -
1.
Turn Left
70
40
45
0
35
-1
0
+ 3
0
+1
- 2
20
36
0
50
30
70
45
35
30
36
50
40
20
عائم
AVL (Double Rotation
)
Case
1
+ & -
2.
Turn Right
70
45
35
30
36
50
40
20
50
45
35
30
36
20
40
70
عائم
AVL (Double Rotation
)
Case
2
- & +
1.
Turn Right
2.
Turn Left
80
70
30
50
60
65
0
55
-1
56
0
- 3
0
+1
0
+ 2
AVL (Double Rotation
)
Case
2
- & +
1.
Turn Right
70
30
50
55
56
80
65
60
80
70
30
50
60
65
0
55
-1
56
0
- 3
0
+1
0
+ 2
AVL (Double Rotation
)
Case
2
2.
Turn Left
80
50
65
70
60
55
56
30
عائم
70
50
55
56
80
65
60
30
Thank You
Explore the intricacies of AVL trees in data structures through a series of lectures at the University of Basrah, Iraq. Delve into concepts such as balance factors, rotations, and single rotation cases to deepen your understanding of maintaining balance in AVL trees. Gain valuable insights from Instructor Ghazwan Abdulnabi Al-Ali to enhance your knowledge in this area.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
3rd Grade College of Computer Science and Information Technology Department of Computer Science Data Structures Lecture 5 AVL Trees Instructor: Ghazwan Abdulnabi Al-Ali University of Basrah, Iraq
Sibling 2
Data Structures University of Basrah Internal 3
Data Structures University of Basrah Ancestors 4
Data Structures University of Basrah Subtree 5
Data Structures University of Basrah AVL 8 balance factor = Left-Right. 5 11 2 6 1 6
Data Structures University of Basrah AVL +2 8 balance factor = left-right. 3-1= +2 5 11 2 6 1 7
Data Structures University of Basrah AVL +2 8 balance factor = left-right. 2-1= +1 +1 5 11 2 6 1 8
Data Structures University of Basrah AVL +2 8 balance factor = left-right. 1-0= +1 +1 5 11 +1 2 6 1 9
Data Structures University of Basrah AVL +2 8 balance factor = left-right. +1 0 0-0= 0 5 11 +1 0 2 6 0 1 10
Data Structures University of Basrah AVL (Single Rotation) Case 1 + 2 + & + Turn Right 8 + 1 0 5 11 +1 0 2 6 0 1 11
Data Structures University of Basrah AVL (Single Rotation) Case 1 + 2 8 + & + Turn Right + 1 0 5 5 11 +1 0 2 8 2 6 11 1 6 0 1 12
Data Structures University of Basrah AVL (Single Rotation) Case 2 - 2 10 - & - Turn Left 0 - 1 5 15 0 20-1 12 300 13
Data Structures University of Basrah AVL (Single Rotation) Case 2 - 2 10 - & - Turn Left 15 0 - 1 5 15 10 20 0 20-1 12 12 5 30 300 14
Data Structures University of Basrah AVL (Double Rotation) Case 1 50 70 30 20 40 35 45 36 15
Data Structures University of Basrah AVL (Double Rotation) Case 1 + 3 50 + & - 1. Turn Left - 2 0 70 30 0 +1 20 40 -1 450 35 2. Turn Right 0 36 16
Data Structures University of Basrah AVL (Double Rotation) Case 1 + 3 50 50 + & - 1. Turn Left - 2 0 40 70 70 30 0 +1 30 20 45 40 -1 450 20 35 35 0 36 36 17
Data Structures University of Basrah AVL (Double Rotation) Case 1 50 40 + & - 2. Turn Right 40 70 30 50 30 45 20 35 45 70 20 35 36 36 18
Data Structures University of Basrah AVL (Double Rotation) Case 2 - 3 50 - & + 1. Turn Right 0 + 2 30 70 +1 0 60 80 -1 650 55 2. Turn Left 560 19
Data Structures University of Basrah AVL (Double Rotation) Case 2 - 3 50 50 - & + 1. Turn Right + 2 0 30 70 30 60 +1 0 60 80 55 70 -1 650 55 80 56 65 560 20
Data Structures University of Basrah AVL (Double Rotation) Case 2 2. Turn Left 60 50 50 70 30 60 55 30 65 80 55 70 56 80 56 65 21
Data Structures University of Basrah Thank You 22
