Understanding AVL Trees in Data Structures: Lecture Insights
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. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
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
