What is AVL trees and example based on AVL Tree

AVL tress in detail

1. AVL Trees
•An AVL tree is a self-balancing binary search tree where the height difference between the
left and right subtrees of any node is at most 1.
•This height difference is also called as balance factor.
•A normal Binary Search Tree can become skewed (unbalanced), leading to inefficient
operations (O(n) complexity in the worst case).

2. •AVL Trees maintain balance automatically, ensuring O(log n) complexity for insertion,
deletion, and search.
•Balance Factor in AVL Trees
The balance factor (BF) of a node is defined as:
BF=Height of Left Subtree−Height of Right Subtree
•A node is:
▪Balanced if BF = -1, 0, or 1
▪Unbalanced if BF < -1 or BF > 1 (Requires rotation)
Rotations in AVL:-
1.Right Rotation (LL Case)
1.First L indicate that imbalance of the node is due to left sub-tree.
2.Second L indicate that new node has been inserted in left sub-tree of left child.
3.When this LL case happens, a single right rotation on the unbalanced node is enough to
restore balance.
4.Example

4. 2.Left Rotation (RR case)
1.First R indicate that imbalance of the node is due to right sub-tree.
2.Second R indicate that new node has been inserted in right sub-tree of right child.
3.When this RR case happens, a single left rotation on the unbalanced node is enough to
restore the balance.
4.Example

5. 3. Left Right Rotation (LR Case)
1.First L indicate that imbalance of the node is due to left sub-tree.
2.Second R indicate that new node has been inserted in right sub-tree of left child.
3.When this LR case happens, 2 rotations are required. (First Left rotation and then Right
rotation)
4.Example

6. 4. Right Left Rotation (RL Case)
1.First R indicate that imbalance of the node is due to right sub-tree.
2.Second L indicate that new node has been inserted in left sub-tree of right child.
3.When this RL case happens, 2 rotations are required. (First Right rotation and then Left
rotation)
4.Example