AVL
🌳 Understanding AVL Trees in Simple Terms
The Post explains the concept of AVL Trees as a smart solution to the imbalance problem in Binary Search Trees (BSTs). Here’s the summary in easy points:
- BST Problem: In the worst case, a BST can grow in one direction (like a linked list). This makes operations as slow as O(n), rather than the efficient O(log n).
- AVL Solution: An AVL tree is a self-balancing BST. After every insertion or deletion, it automatically adjusts itself to keep operations fast — always around O(log n).
- Balance Factor: For each node, it’s calculated as:
Height of left subtree – Height of right subtree
Balanced Condition: A node is balanced if its balance factor is 0, 1, or -1
- Rotation: If the balance factor becomes 2 or -2, the tree is unbalanced. A rotation is applied immediately to restore balance.
🌟 Origin of the Name “AVL Tree”
- AVL meaning: The name AVL comes from the initials of the two Soviet scientists who invented this tree in 1962.
- Inventors:
Adelson-Velsky (Georgy Adelson-Velsky)
Landis (Evgenii Landis)
Full name: In English, it’s called the Adelson-Velsky and Landis Tree.
🧮 Balance Factor Basics
- Definition: For each node,
BF=Height of Left Subtree−Height of Right Subtree
- Interpretation:
- BF = 0 → perfectly balanced
- BF = 1 or -1 → slightly tilted but still balanced
- BF = 2 or -2 → unbalanced → needs rotation
🌳 Applying to the Image:
Let’s check a few nodes from your diagram:
. Root Node 8: Left subtree height = 3 (nodes 3 → 6 → 7)
Right subtree height = 3 (nodes 10 → 14 → 13)
BF = 3–3 = 0 ✅ Balanced
. Node 10: Left subtree height = 0 (no left child)
Right subtree height = 2 (nodes 14 → 13)
BF = 0–2 = -2 ❌ Unbalanced → needs rotation
. Node 3: Left subtree height = 1 (node 1)
Right subtree height = 2 (nodes 6 → 7)
Get Emad Mohamed’s stories in your inbox
Join Medium for free to get updates from this writer.
BF = 1–2 = -1 ✅ Balanced
🔑 Key Takeaway
- To calculate BF: look at each node, measure the height of its left and right subtrees, then subtract.
- If BF ∈ {0, 1, -1} → balanced.
- If BF ∈ {2, -2} → unbalanced → fix with rotation.
👉 In short: AVL Trees keep your searches efficient by ensuring the tree never “leans” too much in one direction.
Single Rotation : Right Rotation (LL Rotation) in an AVL Tree :
- When node 8 has child 3 below it, and both have the same sign → the rotation arrow goes above node 8 .
. Since node 8 balance factor is positive +2 , → the rotation direction is to the right.
this is called Right Rotation (LL Rotation) in an AVL Tree.
Use Case: When tree is left-heavy on the left side
Single Rotation : Left Rotation (RR Rotation) in an AVL Tree :
- When node 3 has child 8 below it, and both have the same sign -ve → the rotation arrow goes above node 3 .
. Since node 3 balance factor is negative -2 , → the rotation direction is to the left.
Use Case: When tree is right-heavy on the right side.
Double Rotation : Left Right Rotation (LR Rotation) in an AVL Tree :
- When node 8 has child 3 below it, and they have different sign → the rotation arrow goes below node 8 .
. Since node 3 balance factor is -1 , → the rotation direction is to the left (LR for the child).
. Since node 8 balance factor is + 2, → the rotation direction is to the right (RR for the parent).
Use Case: When tree is left-heavy but imbalance is on right side of left child
Double Rotation : Right Left Rotation (RL Rotation) in an AVL Tree :
- When node 5has child 8 below it, and they have different sign → the rotation arrow goes below node 5.
. Since node 5 balance factor is +1, → the rotation direction is to the right(RR for the child).
. Since node 5 balance factor is -2 → the rotation direction is to the left (LR for the parent).
Use Case: When tree is Right-heavy but imbalance is on left side of left child.
Time Complexity
- Search: O(log n)
- Insert: O(log n)
- Delete: O(log n)
- Space: O(n)
