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).
How It Works
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) – Left-Left Imbalance
- Left Rotation (RR) – Right-Right Imbalance
- Left-Right Rotation (LR) – Left-Right Imbalance
- Right-Left Rotation (RL) – Right-Left 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)
See what happens with your input
Get a short, step-by-step explanation of this visualization. Turn on AI Summary, then start a fresh run with your input.
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
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