AVL tree stands for Adelson-Velsky and Landis Tree and it is a self-balancing Binary Search tree. AVL tree is the extension of Binary Search tree Data Structure. It reduces the time complexity of the many operations of Binary Search Tree.
The name of this tree Data Structure AVL is named after its inventor Adelson-Velsky and Landis and they publish this algorithm in 1962.
In a Binary Search tree, the searching and inserting can have the complexity of O(n) where n represent the number of nodes, but with AVL tree we can do it with a time complexity of O(log n) which make the AVL more efficient and faster than Binary Search Tree.
AS we said the ALV tree is a Self-Balancing Tree what does it mean? Self-Balancing is a property that helps the tree to form a balanced tree, and a tree would be considered as a balanced tree if the difference of its right subtree and left subtree is between -1 to 1. The height difference of two subtrees is also known as the Balance Factor.
With every Insertion and Deletion operation, the AVL tree performs the self-balancing property which makes the tree structure into a balanced tree.
As AVL tree is an extension of Binary search Tree so it satisfies the Binary Search Tree Properties, which are the key value of the left child should be smaller than Parent and the key value of the Right Child should be greater than the parent.
Self-balancing AVL tree Vs Binary Search Tree
AVL Tree | Binary Search Tree |
Insert Root Node 10 | |
10 / \ / \ |
10 / \ / \ |
Insert 30 | |
10 / \ / \ 30 |
10 / \ / \ 30 |
Insert 40 | |
10 \ \ 30 \ 40 Self-balance 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 in between -1 to 1. 30 / \ / \ 10 40 |
10 \ \ 30 \ 40 |
Balancing Factor
Balancing Factor determine whether the tree is balanced or not If the balancing factor value in between -1 to 1 then the tree would be considered as a balanced tree or else it considered as an unbalanced tree.
If after the insertion or deletion in AVL tree the Balancing Factor becomes more than 1 or less than 1, so the algorithm for self-balancing balance the tree.
A balancing factor shows the difference between the height of the left subtree and the right sub-tree.
Balance Factor = height(Right Sub-Tree) – height(left sub-tree).
Balance Factor Values | Description |
Balance Factor <= -1 | It means the height of left subtree is larger than right subtree |
Balancing Factor == 0 | The height of the left subtree is equal to the height of right subtree |
Balancing Factor >=1 | The right subtree height is larger than the left subtree. |
Complexities
AVL reduce the time complexity of BST for Search, Insert and Delete operations.
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 insertion and Deletion operation, we check for balance factor if the balance factor in between -1 to 1 then we leave the tree, if not we have to balance the tree. To balance the tree we need to rotate the nodes positioning after the insertion and deletion operation so the tree remains balance.
We move the nodes either left or right in order to make the tree balance, in AVL we have a total of four types of rotation which are classified into two types:
- Single Rotation
- Double Rotation
Types of Single Rotation
- Left Rotation
- Right Rotation
Types of Double Rotation
- Left-Right Rotation
- Right-Left Rotation
Single Left Rotation
In Left rotation, each node move position to its left from the current position
10 20 \ / \ 20 ----> 10 30 \ 30
Single Right Rotation:
In this rotation, each node moves to its right from the current position.
30 / 20 ------------> 20 / / \ 10 10 30
Double: Left Right Rotation
In this, we first rotate the node left then right to the current position.
30 30 / / 10 ----> 20 --------> 20 \ / / \ 20 10 10 30
Double: Right Left Rotation
In this rotation, the node moves to right then follow by left rotation.
10 1 \ \ 30 ---------> 2 -----------------> 20 / \ / \ 20 3 10 30
People are also reading: