Lecture 308:- General form of AVL Rotations

AVL tree rotations are operations used to maintain the balance of an AVL tree after insertion or deletion of nodes. There are four types of AVL rotations: Left-Left (LL) rotation, Right-Right (RR) rotation, Left-Right (LR) rotation, and Right-Left (RL) rotation. Each rotation is used to restore the balance of the tree when it becomes unbalanced due to an insertion or deletion.

1. Left-Left (LL) Rotation:

cssCopy code

      a                  b     / \                / \    b   T3   -->       c   a   / \                    / \  c   T2                 T2  T3

1. Right-Right (RR) Rotation:

cssCopy code

    a                    b   / \                  / \  T1  b       -->      a   c     / \              / \    T2  c            T1 T2

1. Left-Right (LR) Rotation:

cssCopy code

    a               a               c   / \             / \            /   \  T1  b    -->    c   b    -->   a     b     / \         / \           / \   / \    c  T4       T1 T3         T1 T2 T3 T4   / \ T2   T3

1. Right-Left (RL) Rotation:

cssCopy code

     a             a             c    / \           / \          /   \   b  T1   -->   b   c   -->  a     b  / \           / \         / \   / \ T4  c         T2  T1       T4 T2 T3 T1   / \ T2  T3

In these rotations, a, b, and c represent nodes, and T1, T2, T3, and T4 represent their respective subtrees.

To understand the need for these rotations, we can visualize the AVL tree as a balanced binary search tree. When we insert a node and it becomes unbalanced, we perform one of these rotations to restore the balance, ensuring that the AVL property (balance factor in the range of [-1, 0, +1]) is maintained throughout the tree.

The choice of rotation depends on the type of imbalance at a particular node and the shape of the subtrees. These rotations play a crucial role in maintaining the logarithmic height of the AVL tree, allowing efficient search, insert, and delete operations with time complexity of O(log n).