An AVL tree (named after inventors Adelson-Velsky and Landis) is a self-balancing binary search tree. In an AVL tree, the heights of the two child subtrees of any node differ by at most one - this is called the balance factor.
Balance Factor = Height(Left Subtree) - Height(Right Subtree)
For any node in an AVL tree:
• Balance Factor must be -1, 0, or 1
• If BF > 1: Left subtree is too heavy
• If BF < -1: Right subtree is too heavy
Left Rotation (LL):
Used when a node becomes right-heavy (BF < -1) and its right child is balanced or right-heavy. The right child moves up to take the place of its parent.
Right Rotation (RR):
Used when a node becomes left-heavy (BF > 1) and its left child is balanced or left-heavy. The left child moves up to take the place of its parent.
Left-Right Rotation (LR):
Two steps:
1. Left rotation on the left child
2. Right rotation on the parent
Used when a node is left-heavy (BF > 1) and its left child is right-heavy.
Right-Left Rotation (RL):
Two steps:
1. Right rotation on the right child
2. Left rotation on the parent
Used when a node is right-heavy (BF < -1) and its right child is left-heavy.
Rotations are performed after insertions or deletions when:
1. The balance factor of any node becomes less than -1 or greater than 1
2. The tree needs to be rebalanced to maintain the AVL property
• Insertion: O(log n)
• Deletion: O(log n)
• Search: O(log n)
The self-balancing property ensures these logarithmic time complexities.
Enter numbers in the input field above to build your AVL tree. Watch how the tree automatically rebalances itself through rotations to maintain the AVL property.