AVL Tree Visualization
Named after its inventors Adelson-Velsky and Landis, an AVL Tree rigorously maintains balance by ensuring that for every node, the difference between the heights of its left and right subtrees is never more than 1. If an operation violates this condition, the tree automatically rebalances itself through a series of rotations. This ensures that operations like search, insert, and delete have a worst-case time complexity of O(log n).
Every time a node is inserted or deleted, the AVL tree checks the balance factor of each affected node. If a node becomes unbalanced, rotations are performed to restore balance. There are four types of rotations:
- Right Rotation (LL) – Applied when a left child’s left subtree causes imbalance.
- Left Rotation (RR) – Applied when a right child’s right subtree causes imbalance.
- Left-Right Rotation (LR) – Applied when a left child’s right subtree causes imbalance.
- Right-Left Rotation (RL) – Applied when a right child’s left subtree causes imbalance.
Step by Step
- Insert or delete a node like in a normal BST.
- Traverse back up to the root, updating height and checking the balance factor of each ancestor.
- If a node is unbalanced, identify the type of rotation needed (LL, RR, LR, RL).
- Perform the rotation to restore the AVL property.
Pseudocode
function rebalance(node):
updateHeight(node)
nodeBf = balanceFactor(node)
if nodeBf > 1:
if balanceFactor(node.left) >= 0:
rotateRight(node)
else:
rotateLeft(node.left)
rotateRight(node)
if nodeBf < -1:
if balanceFactor(node.right) <= 0:
rotateLeft(node)
else:
rotateRight(node.right)
rotateLeft(node)
if node.parent:
rebalance(node.parent)
AI Summary
(5 credits)
Common Interview Questions
What is the balance factor constraint in an AVL Tree?
The balance factor is calculated as: height(leftSubtree) - height(rightSubtree). In an AVL tree, balance factor for every node must be within (-1, 0, +1).
Explain Left-Right (LR) and Right-Left (RL) double rotations in AVL Trees.
LR imbalance occurs when a node is left-heavy, but its left child is right-heavy. Fixed by first performing a Left Rotation on the left child, followed by a Right Rotation on the imbalanced parent node.
💬 Discussion
Sign in to join the discussion
Curious to Learn More?
Hand-picked resources to deepen your understanding
© 2025 See Algorithms. Code licensed under MIT, content under CC BY-NC 4.0