AVL tree stands for AdelsonVelsky and Landis tree, and it is a selfbalancing Binary Search Tree. AVL tree is the extension of the BST data structure. Also, it reduces the time complexity of the many operations of BST. The tree data structure got its name from the name of its inventors, i.e., AdelsonVelsky and Landis. They published the algorithm in 1962. In a binary search tree, searching and inserting can have the complexity of O(n), where n represents the number of nodes. However, with the AVL tree, we can do it with a time complexity of O(log n), which makes it more efficient and faster than a BST. We said that AVL tree is a selfbalancing binary search tree, but what does it mean? A tree will be considered as a balanced tree if the difference of the heights of its right subtree and left subtree is between 1 to 1. Selfbalancing is a property that helps a tree data structure to form a balanced tree. The height difference of two subtrees is known as the Balance Factor. With every insertion and deletion operation, the AVL tree performs the selfbalancing property, which makes the tree data structure a balanced tree. As the AVL tree is an extension of the binary search tree, it satisfies the BST properties, which are that the key value of the left child should be smaller than the parent and the key value of the right child should be greater than the parent.
AVL Tree
Balancing Factor
The Balancing Factor determines whether the tree is balanced or not. If the value of the Balancing Factor is between 1 to 1, then the tree would be considered as a balanced tree. Else, it will be an unbalanced tree. If, after the insertion or deletion operation in an AVL tree, the Balancing Factor becomes more than 1 or less than 1, then the algorithm for selfbalancing will balance the tree. The Balancing Factor shows the difference between the height of the left subtree and the right subtree.
Balancing Factor = height(Right SubTree) – height(left subtree)
The following table gives out information on what the different values of the Balancing Factor mean:
Balance Factor Values  Description 
Balance Factor <= 1  It means the height of the left subtree is larger than the right subtree. 
Balancing Factor = 0  The height of the left subtree is equal to the height of the right subtree. 
Balancing Factor >=1  The height of the right subtree is greater than the height of the left subtree. 
Complexity
AVL reduces the time complexity of BST for search, insert and delete operations. The following table gives out the various complexities of the selfbalancing BST in average and worst cases:
Algorithm  Average case  Worst case 
Space  o(n)  o(n) 
Search  o(log n)  o(log n) 
Insert  o(log n)  o(log n) 
Delete  o(log n)  o(log n) 
AVL Tree Rotation
In AVL, after an insertion or deletion operation, we check for the Balancing Factor. If it is in between 1 to 1, then we leave the tree. Otherwise, we have to balance the tree. To balance the tree, we need to rotate the positioning of the nodes after the insertion or deletion operation. We move the nodes either left or right in order to make the tree a balanced tree. In AVL, we have a total of four types of rotation that are classified into two types:

Single Rotation
 Left Rotation
 Right Rotation

Double Rotation
 LeftRight Rotation
 RightLeft Rotation
1. Single Rotation
a. Single Left Rotation In Single Left Rotation, each node is moved to its left from the current position.
Example:
10 20 \ / \ 20 > 10 30 \ 30
b. Single Right Rotation In this rotation, each node moves to its right from the current position.
Example:
30 / 20 > 20 / / \ 10 10 30
2. Double Rotation
a. LeftRight Rotation In this, we first rotate the node left and then right with respect to the current position.
Example:
30 30 / / 10 > 20 > 20 \ / / \ 20 10 10 30
b. RightLeft Rotation In this type of double rotation, the node moves to the right then to the left w.r.t. to the current position.
Example:
10 1 \ \ 30 > 2 > 20 / \ / \ 20 3 10 30
Selfbalancing AVL Tree vs. Binary Search Tree
AVL Tree  Binary Search Tree 
First Step  Insert Root Node 10  
10 / \ / \ 
10 / \ / \ 
Second Step  Insert 30  
10 / \ / \ 30 
10 / \ / \ 30 
Third Step  Insert 40  
10 \ \ 30 \ 40Selfbalancing by rotation because the height of the right child is 2 and the height of the left child is 0, so the difference is not between 1 to 1. 30 / \ / \ 10 40 
10 \ \ 30 \ 40 
Conclusion
An AVL (AdelsonVelsky and Landis) tree is simply a binary search tree that is selfbalancing. It offers a more efficient way of searching and inserting elements in a tree data structure.
People are also reading: