What if the input to binary search tree comes in a sorted (ascending or descending) manner? It will then look like this −
- It has been discovered that BST's worst-case performance is similar to that of linear search algorithms, i.e. O (n).
- We can't forecast data patterns and frequencies in real-time data. As a result, there is a need to balance out the present BST.
- AVL trees are height-balancing binary search trees named after their inventors Adelson, Velski, and Landis.
- The AVL tree compares the heights of the left and right sub-trees and ensures that they do not deviate by more than one.
- The Balance Factor is the name given to this variation.
- Here we see that the first tree is balanced and the next two trees are not balanced −
- In the second tree, the left subtree of C has height 2 and the right subtree has height 0, so the difference is 2.
- In the third tree, the right subtree of A has height 2 and the left is missing, so it is 0, and the difference is 2 again. AVL tree permits difference (balance factor) to be only 1.
BalanceFactor = height(left-sutree) − height(right-sutree)
- If the difference in the height of left and right sub-trees is more than 1, the tree is balanced using some rotation techniques.
AVL Rotations
To balance itself, an AVL tree may perform the following four kinds of rotations −
- Left rotation
- Right rotation
- Left-Right rotation
- Right-Left rotation
- The first two rotations are single rotations, followed by two double rotations. A tree of at least height 2 is required to have an imbalanced tree. Let's take a look at them one by one using this simple tree.
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 −
- In our example, node A has become unbalanced as a node is inserted in the right subtree of A's right subtree. We perform the left rotation by making A the left-subtree of B.
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.
- As depicted, the unbalanced node becomes the right child of its left child by performing a right rotation.
Left-Right Rotation
- Double rotations are a more complicated variation of previously explained rotations.
- Take note of each action performed during rotation to better comprehend them.
- First, let's look at how to perform a Left-Right rotation. A combination of left and right rotations is known as a left-right rotation.
