An AVL tree is a self-balancing binary search tree. A binary tree is said to be balanced, if the difference between the heights of left and right subtrees of every node in the tree is either -1, 0 or +1 . This is known as the Balance Factor.
Nomen4Omen [CC BY-SA 3.0 de]
Why is balancing important?
It is observed that a binary search tree’s worst time complexity is similar to a linear search algorithm. This is because one side of the tree has more elements than the other side.
In real-world data, we cannot predict the structure that our tree will resemble, hence it may be possible that the binary search tree performs worse than expected.
To keep the binary search tree’s performance intact, the tree is kept balanced so that one side is not heavier (has more children) than the other. This ensures that the binary search has equal elements to work with on both sides.
The balance factor can be derived as:
Balance Factor = height(left-subtree) − height(right-subtree)
If the difference in the height is found to be greater than 1, the tree is balanced using 4 rotation techniques. These techniques are generally applied when inserting or deleting nodes in the tree.
AVL Rotations
To balance itself, an AVL tree performs the following kinds of rotations:
Left rotation
The balance property, in this case, is restored by a single left rotation.
Right rotation
The balance property, in this case, is restored by a single right rotation.
Tar-Elessar [CC BY-SA 4.0]
Left-Right rotation
The balance property, in this case, is restored by a left rotation followed by a right rotation.
Henning.H [CC BY-SA 2.0 de]
Right-Left rotation
The balance property, in this case, is restored by a right rotation followed by a left rotation.
Henning.H [CC BY-SA 2.0 de]
Videos
Shorter
Longer