AVL Trees: A Self-balancing Binary Search Tree

 
AVL TREE
 
Prof. Manjusha Amritkar
Information Technology Department
 
International Institute of Information Technology, I²IT
Binary Search Tree
 
•
E.g. 2,4,6,8,10
 
 
 
•
Right skewed tree
 
•
Time needed to perform insertion ,deletion and many other
operations is O(N) in worst case.
•
We need tree with small height with Log N
•
Such trees are called as Balanced Binary Search Tree
•
e.g AVL tree, Red Black Tree
International Institute of Information Technology, I²IT, P-14, Rajiv Gandhi Infotech Park, Hinjawadi Phase 1, Pune - 411 057
 Phone - +91 20 22933441/2/3 | Website - www.isquareit.edu.in | Email - info@isquareit.edu.in
AVL Tree
 
•
AVL tree Named after their inventor 
A
delson, 
V
elski &
L
andis, is a self-balancing Binary Search Tree (BST) where
the difference between heights of left and right subtrees
cannot be more than one for all nodes.
 
•
The difference between the heights is called
as 
balanced factor (BF)
 
•
BF = height (left subtree) – height (right subtree)
 
•
The tree is balanced when BF is -1, 0, 1
International Institute of Information Technology, I²IT, P-14, Rajiv Gandhi Infotech Park, Hinjawadi Phase 1, Pune - 411 057
 Phone - +91 20 22933441/2/3 | Website - www.isquareit.edu.in | Email - info@isquareit.edu.in
AVL Tree Rotations
 
•
If the difference is more than one then the tree is to be
balanced using rotations.
 
 
•
Left rotation (LL)
   Right rotation (RR)
   Left-Right rotation (LR)
   Right-Left rotation (RL)
International Institute of Information Technology, I²IT, P-14, Rajiv Gandhi Infotech Park, Hinjawadi Phase 1, Pune - 411 057
 Phone - +91 20 22933441/2/3 | Website - www.isquareit.edu.in | Email - info@isquareit.edu.in
 
Left Rotation
 
 
•
If a tree becomes unbalanced, when a node is inserted into the
right subtree of the right subtree, then we perform a single
left rotation
 
International Institute of Information Technology, I²IT, P-14, Rajiv Gandhi Infotech Park, Hinjawadi Phase 1, Pune - 411 057
 Phone - +91 20 22933441/2/3 | Website - www.isquareit.edu.in | Email - info@isquareit.edu.in
 
Right Rotation
 
 
•
AVL tree may become unbalanced, if a node is inserted in the
left subtree of the left subtree. The tree then needs a right
rotation
 
International Institute of Information Technology, I²IT, P-14, Rajiv Gandhi Infotech Park, Hinjawadi Phase 1, Pune - 411 057
 Phone - +91 20 22933441/2/3 | Website - www.isquareit.edu.in | Email - info@isquareit.edu.in
 
Left Right Rotations
 
•
A node has been inserted into the right subtree of the left
subtree. This makes C an unbalanced node. These scenarios
cause AVL tree to perform left-right rotation.
 
International Institute of Information Technology, I²IT, P-14, Rajiv Gandhi Infotech Park, Hinjawadi Phase 1, Pune - 411 057
 Phone - +91 20 22933441/2/3 | Website - www.isquareit.edu.in | Email - info@isquareit.edu.in
LR Rotation
 
Right Left Rotations
 
•
A node has been inserted into the left subtree of the right
subtree. This makes A, an unbalanced node with balance factor
2.
 
International Institute of Information Technology, I²IT, P-14, Rajiv Gandhi Infotech Park, Hinjawadi Phase 1, Pune - 411 057
 Phone - +91 20 22933441/2/3 | Website - www.isquareit.edu.in | Email - info@isquareit.edu.in
RL Rotation
 
Example: Construct an AVL Tree by inserting numbers
from 1 to 8.
 
International Institute of Information Technology, I²IT, P-14, Rajiv Gandhi Infotech Park, Hinjawadi Phase 1, Pune - 411 057
 Phone - +91 20 22933441/2/3 | Website - www.isquareit.edu.in | Email - info@isquareit.edu.in
 
Example: Construct an AVL Tree by inserting numbers
from 1 to 8.
 
International Institute of Information Technology, I²IT, P-14, Rajiv Gandhi Infotech Park, Hinjawadi Phase 1, Pune - 411 057
 Phone - +91 20 22933441/2/3 | Website - www.isquareit.edu.in | Email - info@isquareit.edu.in
 
Example: Construct an AVL Tree by inserting numbers
from 1 to 8.
 
International Institute of Information Technology, I²IT, P-14, Rajiv Gandhi Infotech Park, Hinjawadi Phase 1, Pune - 411 057
 Phone - +91 20 22933441/2/3 | Website - www.isquareit.edu.in | Email - info@isquareit.edu.in
 
Example: Construct an AVL Tree by inserting numbers
from 1 to 8.
 
International Institute of Information Technology, I²IT, P-14, Rajiv Gandhi Infotech Park, Hinjawadi Phase 1, Pune - 411 057
 Phone - +91 20 22933441/2/3 | Website - www.isquareit.edu.in | Email - info@isquareit.edu.in
 
Example: Construct an AVL Tree by inserting numbers
from 1 to 8.
 
International Institute of Information Technology, I²IT, P-14, Rajiv Gandhi Infotech Park, Hinjawadi Phase 1, Pune - 411 057
 Phone - +91 20 22933441/2/3 | Website - www.isquareit.edu.in | Email - info@isquareit.edu.in
 
Example: Construct an AVL Tree by inserting numbers
from 1 to 8.
 
International Institute of Information Technology, I²IT, P-14, Rajiv Gandhi Infotech Park, Hinjawadi Phase 1, Pune - 411 057
 Phone - +91 20 22933441/2/3 | Website - www.isquareit.edu.in | Email - info@isquareit.edu.in
 
Example: Construct an AVL Tree by inserting numbers
from 50,25,10,5,7,3,30,20,8,15.
 
•
Insert 50
 
 
 
•
Insert 25
50
 
0
Tree is balanced
Tree is balanced
50
 
1
Tree is balanced
Tree is balanced
25
 
0
 
International Institute of Information Technology, I²IT, P-14, Rajiv Gandhi Infotech Park, Hinjawadi Phase 1, Pune - 411 057
 Phone - +91 20 22933441/2/3 | Website - www.isquareit.edu.in | Email - info@isquareit.edu.in
 
Example: Construct an AVL Tree by inserting numbers
from 50,25,10,5,7,3,30,20,8,15.
 
•
Insert 10
 
 
 
Tree is imbalanced
Tree is imbalanced
Tree is balanced
Tree is balanced
 
International Institute of Information Technology, I²IT, P-14, Rajiv Gandhi Infotech Park, Hinjawadi Phase 1, Pune - 411 057
 Phone - +91 20 22933441/2/3 | Website - www.isquareit.edu.in | Email - info@isquareit.edu.in
RR Rotation
 
Example: Construct an AVL Tree by inserting numbers
from 50,25,10,5,7,3,30,20,8,15.
 
•
Insert 5                                   insert 7
 
 
 
Tree is balanced
Tree is balanced
Tree is imbalanced
Tree is imbalanced
Tree is balanced
Tree is balanced
 
International Institute of Information Technology, I²IT, P-14, Rajiv Gandhi Infotech Park, Hinjawadi Phase 1, Pune - 411 057
 Phone - +91 20 22933441/2/3 | Website - www.isquareit.edu.in | Email - info@isquareit.edu.in
LR Rotation
 
Example: Construct an AVL Tree by inserting numbers
from 50,25,10,5,7,3,30,20,8,15.
Tree is imbalanced
Tree is imbalanced
25
 
2
7
 
1
50
 
0
5
 
1
7
 
0
5
25
 
0
3
 
 0
 
 0
Tree is balanced
Tree is balanced
10
 
0
3
 
0
50
 
0
 
1
10
 
International Institute of Information Technology, I²IT, P-14, Rajiv Gandhi Infotech Park, Hinjawadi Phase 1, Pune - 411 057
 Phone - +91 20 22933441/2/3 | Website - www.isquareit.edu.in | Email - info@isquareit.edu.in
 
•
Insert 3
 
 
LL Rotation
 
Example: Construct an AVL Tree by inserting numbers
from 50,25,10,5,7,3,30,20,8,15.
 
•
Insert 30                           insert 20
 
 
Tree is imbalanced
Tree is imbalanced
Tree is balanced
Tree is balanced
20
 
 0
 
International Institute of Information Technology, I²IT, P-14, Rajiv Gandhi Infotech Park, Hinjawadi Phase 1, Pune - 411 057
 Phone - +91 20 22933441/2/3 | Website - www.isquareit.edu.in | Email - info@isquareit.edu.in
RL Rotation
 
References
 
•
http://www.btechsmartclass.com/data_structures/avl-trees.html
 
International Institute of Information Technology, I²IT, P-14, Rajiv Gandhi Infotech Park, Hinjawadi Phase 1, Pune - 411 057
 Phone - +91 20 22933441/2/3 | Website - www.isquareit.edu.in | Email - info@isquareit.edu.in
 
International Institute of Information Technology, I²IT, P-14, Rajiv Gandhi Infotech Park, Hinjawadi Phase 1, Pune - 411 057
 Phone - +91 20 22933441/2/3 | Website - www.isquareit.edu.in | Email - info@isquareit.edu.in
 
E-mail: 
manjushaa@isquareit.edu.in
 
Thank You

								

								
								

										

												
Slide Note

												

										

								


								
						

							
						


							

								

									
										
Embed
									
									
										
Share
									

									
									
									

								

								
							


							

							 
 							 
 							 
						  


							
							

								
AVL trees, named after their inventors Adelson-Velski & Landis, are self-balancing binary search trees where the height difference between left and right subtrees is limited. This ensures a balanced factor of -1, 0, or 1, leading to efficient operations such as insertion and deletion. Rotation techniques like LL, RR, LR, and RL help maintain balance in AVL trees, ensuring optimal performance in data structures.


								
    
																		
  •   AVL Trees
    • 
																	
  •    Self-balancing
    • 
																	
  •    Binary Search Tree
    • 
																	
  •    Rotation Techniques
    • 
																	
  •    Data Structures
    • 
																

								

								

									

										darci
										

											 darci Follow
											

										

									

									
Uploaded on Jul 20, 2024 | 5 Views

								

								


								

									
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

								

								
  1. AVL TREE Prof. Manjusha Amritkar Information Technology Department International Institute of Information Technology, I  IT www.isquareit.edu.in 
    2. 
            
            
            
  2. Binary Search Tree     E.g. 2,4,6,8,10 2 4 6 8     Right skewed tree 10     Time needed to perform insertion ,deletion and many other  operations is O(N) in worst case.     We need tree with small height with Log N     Such trees are called as Balanced Binary Search Tree      e.g AVL tree, Red Black Tree International Institute of Information Technology, I  IT, P-14, Rajiv Gandhi Infotech Park, Hinjawadi Phase 1, Pune - 411 057   Phone - +91 20 22933441/2/3 | Website - www.isquareit.edu.in | Email - info@isquareit.edu.in 
    3. 
            
            
            
  3. AVL Tree     AVL tree Named after their inventor Adelson, Velski &  Landis, is a self-balancing Binary Search Tree (BST) where  the difference between heights of left and right subtrees  cannot be more than one for all nodes.     The difference between the heights is called  as balanced factor (BF)     BF = height (left subtree)     height (right subtree)     The tree is balanced when BF is -1, 0, 1 International Institute of Information Technology, I  IT, P-14, Rajiv Gandhi Infotech Park, Hinjawadi Phase 1, Pune - 411 057   Phone - +91 20 22933441/2/3 | Website - www.isquareit.edu.in | Email - info@isquareit.edu.in 
    4. 
            
            
            
  4. AVL Tree Rotations     If the difference is more than one then the tree is to be  balanced using rotations.     Left rotation (LL)    Right rotation (RR)    Left-Right rotation (LR)    Right-Left rotation (RL) International Institute of Information Technology, I  IT, P-14, Rajiv Gandhi Infotech Park, Hinjawadi Phase 1, Pune - 411 057   Phone - +91 20 22933441/2/3 | Website - www.isquareit.edu.in | Email - info@isquareit.edu.in 
    5. 
            
            
            
  5. Left Rotation     If a tree becomes unbalanced, when a node is inserted into the  right subtree of the right subtree, then we perform a single  left rotation  International Institute of Information Technology, I  IT, P-14, Rajiv Gandhi Infotech Park, Hinjawadi Phase 1, Pune - 411 057   Phone - +91 20 22933441/2/3 | Website - www.isquareit.edu.in | Email - info@isquareit.edu.in 
    6. 
            
            
            
  6. Right Rotation     AVL tree may become unbalanced, if a node is inserted in the  left subtree of the left subtree. The tree then needs a right  rotation International Institute of Information Technology, I  IT, P-14, Rajiv Gandhi Infotech Park, Hinjawadi Phase 1, Pune - 411 057   Phone - +91 20 22933441/2/3 | Website - www.isquareit.edu.in | Email - info@isquareit.edu.in 
    7. 
            
            
            
  7. Left Right Rotations     A node has been inserted into the right subtree of the left  subtree. This makes C an unbalanced node. These scenarios  cause AVL tree to perform left-right rotation. LR Rotation International Institute of Information Technology, I  IT, P-14, Rajiv Gandhi Infotech Park, Hinjawadi Phase 1, Pune - 411 057   Phone - +91 20 22933441/2/3 | Website - www.isquareit.edu.in | Email - info@isquareit.edu.in 
    8. 
            
            
            
  8. Right Left Rotations     A node has been inserted into the left subtree of the right  subtree. This makes A, an unbalanced node with balance factor  2. RL Rotation International Institute of Information Technology, I  IT, P-14, Rajiv Gandhi Infotech Park, Hinjawadi Phase 1, Pune - 411 057   Phone - +91 20 22933441/2/3 | Website - www.isquareit.edu.in | Email - info@isquareit.edu.in 
    9. 
            
            
            
  9. Example: Construct an AVL Tree by inserting numbers  from 1 to 8. International Institute of Information Technology, I  IT, P-14, Rajiv Gandhi Infotech Park, Hinjawadi Phase 1, Pune - 411 057   Phone - +91 20 22933441/2/3 | Website - www.isquareit.edu.in | Email - info@isquareit.edu.in 
    10. 
            
            
            
  10. Example: Construct an AVL Tree by inserting numbers  from 1 to 8. International Institute of Information Technology, I  IT, P-14, Rajiv Gandhi Infotech Park, Hinjawadi Phase 1, Pune - 411 057   Phone - +91 20 22933441/2/3 | Website - www.isquareit.edu.in | Email - info@isquareit.edu.in 
    11. 
            
            
            
  11. Example: Construct an AVL Tree by inserting numbers  from 1 to 8. International Institute of Information Technology, I  IT, P-14, Rajiv Gandhi Infotech Park, Hinjawadi Phase 1, Pune - 411 057   Phone - +91 20 22933441/2/3 | Website - www.isquareit.edu.in | Email - info@isquareit.edu.in 
    12. 
            
            
            
  12. Example: Construct an AVL Tree by inserting numbers  from 1 to 8. International Institute of Information Technology, I  IT, P-14, Rajiv Gandhi Infotech Park, Hinjawadi Phase 1, Pune - 411 057   Phone - +91 20 22933441/2/3 | Website - www.isquareit.edu.in | Email - info@isquareit.edu.in 
    13. 
            
            
            
  13. Example: Construct an AVL Tree by inserting numbers  from 1 to 8. International Institute of Information Technology, I  IT, P-14, Rajiv Gandhi Infotech Park, Hinjawadi Phase 1, Pune - 411 057   Phone - +91 20 22933441/2/3 | Website - www.isquareit.edu.in | Email - info@isquareit.edu.in 
    14. 
            
            
            
  14. Example: Construct an AVL Tree by inserting numbers  from 1 to 8. International Institute of Information Technology, I  IT, P-14, Rajiv Gandhi Infotech Park, Hinjawadi Phase 1, Pune - 411 057   Phone - +91 20 22933441/2/3 | Website - www.isquareit.edu.in | Email - info@isquareit.edu.in 
    15. 
            
            
            
  15. Example: Construct an AVL Tree by inserting numbers  from 50,25,10,5,7,3,30,20,8,15.     Insert 50 0 Tree is balanced 50     Insert 25 1 Tree is balanced 50 0 25 International Institute of Information Technology, I  IT, P-14, Rajiv Gandhi Infotech Park, Hinjawadi Phase 1, Pune - 411 057   Phone - +91 20 22933441/2/3 | Website - www.isquareit.edu.in | Email - info@isquareit.edu.in 
    16. 
            
            
            
  16. Example: Construct an AVL Tree by inserting numbers  from 50,25,10,5,7,3,30,20,8,15.     Insert 10 2 1 50 25 1 RR Rotation 0 0 25 10 50 0 10 Tree is balanced Tree is imbalanced International Institute of Information Technology, I  IT, P-14, Rajiv Gandhi Infotech Park, Hinjawadi Phase 1, Pune - 411 057   Phone - +91 20 22933441/2/3 | Website - www.isquareit.edu.in | Email - info@isquareit.edu.in 
    17. 
            
            
            
  17. Example: Construct an AVL Tree by inserting numbers  from 50,25,10,5,7,3,30,20,8,15.     Insert 5                                   insert 7 1 2 1 25 25 25 2 1 0 0 0 0 LR Rotation 10 10 50 50 7 50 -1 0 0 0 5 5 5 10 0 Tree is imbalanced Tree is balanced Tree is balanced 7 International Institute of Information Technology, I  IT, P-14, Rajiv Gandhi Infotech Park, Hinjawadi Phase 1, Pune - 411 057   Phone - +91 20 22933441/2/3 | Website - www.isquareit.edu.in | Email - info@isquareit.edu.in 
    18. 
            
            
            
  18. Example: Construct an AVL Tree by inserting numbers  from 50,25,10,5,7,3,30,20,8,15.     Insert 3 2 0 25 7 1 0 1 0 7 50 LL Rotation 5 25 1 0 0 0 0 5 10 10 3 50 0 3 Tree is imbalanced Tree is balanced International Institute of Information Technology, I  IT, P-14, Rajiv Gandhi Infotech Park, Hinjawadi Phase 1, Pune - 411 057   Phone - +91 20 22933441/2/3 | Website - www.isquareit.edu.in | Email - info@isquareit.edu.in 
    19. 
            
            
            
  19. Example: Construct an AVL Tree by inserting numbers  from 50,25,10,5,7,3,30,20,8,15.     Insert 30                           insert 20 0 -2 -1 10 7 1 7 0 1 1 RL Rotation 1 -1 7 25 5 25 1 5 1 25 0 -1 0 0 1 0 5 0 1 8 20 10 3 50 50 0 1 10 3 0 0 50 0 8 3 20 0 15 30 50 30 0 Tree is balanced 30 Tree is imbalanced 15 International Institute of Information Technology, I  IT, P-14, Rajiv Gandhi Infotech Park, Hinjawadi Phase 1, Pune - 411 057   Phone - +91 20 22933441/2/3 | Website - www.isquareit.edu.in | Email - info@isquareit.edu.in 
    20. 
            
            
            
  20. References     http://www.btechsmartclass.com/data_structures/avl-trees.html International Institute of Information Technology, I  IT, P-14, Rajiv Gandhi Infotech Park, Hinjawadi Phase 1, Pune - 411 057   Phone - +91 20 22933441/2/3 | Website - www.isquareit.edu.in | Email - info@isquareit.edu.in 
    21. 
            
            
            
  21. Thank You E-mail: manjushaa@isquareit.edu.in International Institute of Information Technology, I  IT, P-14, Rajiv Gandhi Infotech Park, Hinjawadi Phase 1, Pune - 411 057   Phone - +91 20 22933441/2/3 | Website - www.isquareit.edu.in | Email - info@isquareit.edu.in 
    22. 
            
            
            
							

							

					

					
					
					

						
Related

						

						


							
							
							
							

						

							

									

      

        
          

            

              Best Tree Removal in Heathmont
            

            

              
Best Tree Removal in Heathmont

              
jack4

            

          

        
      


     

      

        
          

            

              Looking for the best Tree Lopping in Tumbi Umbi
            

            

              
Looking for the best Tree Lopping in Tumbi Umbi

              
elen

            

          

        
      


     

      

        
          

            

              Exploring Trees Data Structures Using C - Second Edition
            

            

              
Exploring Trees Data Structures Using C - Second Edition

              
araminta

            

          

        
      


     

      

        
          

            

              Binary Heaps: Efficient Data Structure for Priority Queue Operations
            

            

              
Binary Heaps: Efficient Data Structure for Priority Queue Operations

              
elea_53

            

          

        
      


     

      

        
          

            

              Trees and Binary Trees in Data Structures
            

            

              
Trees and Binary Trees in Data Structures

              
jobe_so

            

          

        
      


     

      

        
          

            

              Informed and Uninformed Search Algorithms in Artificial Intelligence
            

            

              
Informed and Uninformed Search Algorithms in Artificial Intelligence

              
aub_l

            

          

        
      


     

      

        
          

            

              Binary Search Trees and Tree Traversal Methods
            

            

              
Binary Search Trees and Tree Traversal Methods

              
khal_531

            

          

        
      


     

      

        
          

            

              AVL and B-Trees in CSE 332 Autumn 2023
            

            

              
AVL and B-Trees in CSE 332 Autumn 2023

              
chea_i

            

          

        
      


     

      

        
          

            

              Priority Queues and Heaps in CSE 373 Lecture
            

            

              
Priority Queues and Heaps in CSE 373 Lecture

              
sdey

            

          

        
      


     

      

        
          

            

              Binary Number System in Mathematics
            

            

              
Binary Number System in Mathematics

              
bond_eb

            

          

        
      


     

      

        
          

            

              Red-Black Trees for Balanced Search Structures
            

            

              
Red-Black Trees for Balanced Search Structures

              
onesti

            

          

        
      


     

      

        
          

            

              Height-Balanced Binary Trees and AVL Trees
            

            

              
Height-Balanced Binary Trees and AVL Trees

              
anava

            

          

        
      


     

      

        
          

            

              Balanced Search Trees and Red-Black Trees
            

            

              
Balanced Search Trees and Red-Black Trees

              
gfaus

            

          

        
      


     

      

        
          

            

              Spanning Trees and Minimum Spanning Trees
            

            

              
Spanning Trees and Minimum Spanning Trees

              
heda_3

            

          

        
      


     

      

        
          

            

              Trees and Optimality Criteria
            

            

              
Trees and Optimality Criteria

              
kymiya

            

          

        
      


     

      

        
          

            

              Solving the Apple Tree and Conifer Tree Pattern Puzzle
            

            

              
Solving the Apple Tree and Conifer Tree Pattern Puzzle

              
nhadd

            

          

        
      


     

      

        
          

            

              Binary Trees in Computer Science
            

            

              
Binary Trees in Computer Science

              
carmanil

            

          

        
      


     

      

        
          

            

              AVL Trees: Operations, Insertion, and Deletion
            

            

              
AVL Trees: Operations, Insertion, and Deletion

              
yase

            

          

        
      


     

      

        
          

            

              Binary Representation of Numbers with Fractions
            

            

              
Binary Representation of Numbers with Fractions

              
gra_m

            

          

        
      


     

      

        
          

            

              Unrooted Trees in Phylogenetics
            

            

              
Unrooted Trees in Phylogenetics

              
jets_849

            

          

        
      


     

      

        
          

            

              Trees in Discrete Structures
            

            

              
Trees in Discrete Structures

              
rosenfeld_d

            

          

        
      


     

      

        
          

            

              Data Structure Concepts: AVL Trees and B-Trees
            

            

              
Data Structure Concepts: AVL Trees and B-Trees

              
jac_bu

            

          

        
      


     							

						

					

					

				


				

			

		
		

			

				
				

					
More Related Content

					

						

														

					

				

				
			

		












 





  
  
  



giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#