AVL Tree

It has been discovered that the worst-case performance of BST is similar to that of linear search algorithms, namely O (n). We cannot 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 the difference is less than one. This distinction is known as the Balance Factor.

Here we see that the first tree is balanced and the next two trees are not balanced −

Unbalanced AVL Trees

The left subtree of C in the second tree has a height of 2 and the right subtree has a height of 0, hence the difference is 2. The difference is 2 again in the third tree, since the right subtree of A has height 2 and the left is missing, therefore it is 0. The AVL tree allows only one difference (balancing factor).
BalanceFactor = height(left-subtree) − height(right-subtree)

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

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 −

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.

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 slightly complex version of already explained versions of rotations. To understand them better, we should take note of each action performed while rotation. Let’s first check how to perform Left-Right rotation. A left-right rotation is a combination of left rotation followed by right rotation.

StateAction
Right RotationA node has been inserted into the right subtree of the left subtree. This makes C an unbalanced node. These scenarios cause AVL tree to perform left-right rotation.
Left RotationWe first perform the left rotation on the left subtree of C. This makes A, the left subtree of B.
Left RotationNode C is still unbalanced, however now, it is because of the left-subtree of the left-subtree.
Right RotationWe shall now right-rotate the tree, making B the new root node of this subtree. C now becomes the right subtree of its own left subtree.
Balanced Avl TreeThe tree is now balanced.

Right-Left Rotation

The second type of double rotation is Right-Left Rotation. It is a combination of right rotation followed by left rotation.

StateAction
Left Subtree of Right SubtreeA node has been inserted into the left subtree of the right subtree. This makes A, an unbalanced node with balance factor 2.
Subtree Right RotationFirst, we perform the right rotation along C node, making C the right subtree of its own left subtree B. Now, B becomes the right subtree of A.
Right Unbalanced TreeNode A is still unbalanced because of the right subtree of its right subtree and requires a left rotation.
Left RotationA left rotation is performed by making B the new root node of the subtree. A becomes the left subtree of its right subtree B.
Balanced AVL TreeThe tree is now balanced.
0

Leave a Comment

Your email address will not be published. Required fields are marked *

11 + 19 =