AVL trees are selfbalancing Binary Search Trees (BST) that was invented by Adelson, Velski and Landis. Let’s consider the following:
 AVL Tree Balance Factor
 How to Perform Rotation in AVL Trees
 Other Data Structure and Algorithm Tutorials
1. AVL Tree Balance Factor
In AVL trees, the difference between the depths of the left and right subtrees should be at most 1 for every subtree.
Take for example the two trees in Figure 1a and 1b.
Figure 1a  Figure 1b 
Balance Factor = 3 – 0 = 3  Balance Factor = 3 – 1 = 2 
In Figure 1a, consider the root node 33. The right subtree has a height of 3 and the left subtree has a height of 0. In this case, the difference between the height of the left subtree and the height of the right subtree is 3 – 0 = 3
In Figure 1b, consider the root node, 48. The right subtree has a height of 1 and the left subtree has a height of 3. In this case, the difference between the height of the left subtree and the height of the right subtree is 3 – 1 = 2.
In both cases, we say that the tree is not balanced.
This difference is called the Balance Factor and is given by:
Balance Factor = height(left subtree) – height (right subtree)
Note that the balance factor cannot be negative. You always need to subtract the bigger number from the smaller number
Each time an AVL tree becomes unbalanced(balancing factor is more than 1) due to insertion or deletion, we need to perform a rotation to make the tree balanced. Rotation is also called rebalancing.
2. How to Perform AVL Tree Rotations
The different kinds of rotations that can be performed in an AVL tree to make is balanced includes:
 Left Rotation
 Right Rotation
 LeftRight Rotation
 RightLeft Rotation
We would discuss these four types of rotations with examples.
Left Rotation
This is an example of simple rotation and is performed in just one step where the root node of the tree moved to the left. This is illustrated in Figure 2a, 2b and 2c.
Figure 2a  Figure 2b  Figure 2c 
Unbalanced Tree (BST)  Left Rotation  Balanced Tree (AVL Tree) 
During a left rotation, the element at the root position(60) becomes the left subtree, while the element previously at the right subtree(84) moves to the root position. The right subtree of 84 remains unchanged.
Right Rotation
This is also an example of simple rotation performed in just one step. In the case of right rotation, the root node moves to the right. This is shown in Figure 3a, 3b and 3c
Figure 3a  Figure 3b  Figure 3c 
Unbalanced Tree (BST)  Left Rotation  Balanced Tree (AVL Tree) 
During a left rotation as shown, the element at the root position(100) becomes the right subtree, while the element previously at the left subtree(84) moves to the root position. The right subtree of 84 remains unchanged.
LeftRight Rotation
This is an example of doublerotation where a left rotation is performed followed by a right rotation. This is required if the unbalanced is caused by the right subtree of the left subtree. This is illustrated in Figure 4a to 4e
State  Action 
Figure 4a
Insertion of the node 84 as the right subtree of 60 makes the tree unbalanced. This is because of the right subtree fo the left subtree. Therefore we need to perform a leftright rotation to make the tree balanced again. 

Figure 4b
The first step is to perform a left rotation on the node 60. This would make 84 the left subtree of 100 and 60 becomes the left subtree of 84 

Figure 4c
At this point, the tree is still unbalanced at the root node 100. This is because of the left subtree of the left subtree 

Figure 4d
We now perform a right rotation. This means moving 84 to the root node and moving the root node (100) as the right subtree. 

Figure 4e
The tree is now balanced. 
RightLeft Rotation
This is also an example of doublerotation where a right rotation is performed followed by a left rotation. This is required if the unbalanced is caused by the left subtree of the right subtree. This is illustrated in Figure 5a to 5e
State  Action 
Figure 5a
Insertion of the node 84 as the leftsubtree of 100 makes the tree unbalanced. This is because of the left subtree fo the right subtree. Therefore we need to perform a rightleft rotation to make the tree balanced again. 

Figure 5b
The first step is to perform a right rotation on the node 100. This would make 84 the right subtree of 60. And 100 becomes the right subtree of 84 

Figure 5c
At this point, the tree is still unbalanced at the root node 60. This is because of the right subtree of the right subtree 

Figure 5d
We now perform a left rotation. This means moving 84 to the root node and moving the root node (60) as the left subtree. 

Figure 5e
The tree is now balanced. 
This is how to perform rotations on AVL trees.
3. Check these Data Structure and Algorithms Tutorials
 Skip Lists and How They Work
 Perfect Hashing – How it Works
 Linear Probing, Quadratic Probing and Double Hashing
 Hashing With Open Addressing
 Universal Hashing
 Search Time Under Simple Uniform Hashing
 Hash Tables – Hashing With Chaining
 Introduction to Hash Tables and Direct Addressing
 Recurrences in Divide and Conquer Algorithm
 How Bloom Filters Work
 How Cuckoo Hashing Works
 Introduction to AVL Trees (With Examples)
One Comment on “Introduction to AVL Trees (With Examples)”