Chapter 28: DSA AVL Trees

DSA AVL Trees – Let’s learn this topic properly and in depth, like I’m sitting next to you with a whiteboard, drawing trees step by step, explaining every concept slowly and clearly, showing rotations with detailed examples, and most importantly telling you why AVL trees exist, when they are useful, and how they differ from ordinary BSTs.

What is an AVL Tree?

An AVL Tree is a self-balancing Binary Search Tree (BST) where the height difference (called balance factor) between the left and right subtrees of every node is at most 1.

It was the first self-balancing BST ever invented (by Adelson-Velsky and Landis in 1962 — hence AVL).

The key property:

Balance factor of a node = height(left subtree) − height(right subtree)

And this balance factor must always be −1, 0, or +1 for every node in the tree.

If after any insertion or deletion the balance factor of any node becomes +2 or −2, we immediately perform rotations to restore the balance.

Why do we need AVL Trees? (very important motivation)

Normal Binary Search Tree problems:

• If you insert elements in sorted order (or almost sorted) → tree becomes skewed (like a linked list)

Example:

Insert 10, 20, 30, 40, 50, 60 → tree becomes:

• Height = O(n) instead of O(log n)
• Search / insert / delete → O(n) worst case (same as linked list)

AVL tree fixes this by automatically rebalancing itself after every insert/delete operation so that:

• Height is always kept O(log n)
• All operations remain O(log n) in worst case (not just average)

Balance Factor & Height

Height of a node = longest path from that node to a leaf (leaf height = 0)

Balance Factor = height(left) − height(right)

Allowed values: −1, 0, +1

Examples:

→ This tree is unbalanced → we must rotate

The Four Possible Imbalance Cases & Rotations

When balance factor becomes +2 or −2, we fix it using rotations.

There are four cases:

1. Left-Left (LL) violation → balance = +2 and left child balance ≥ 0 → Right Rotation (single rotation)
2. Left-Right (LR) violation → balance = +2 and left child balance = −1 → Left-Right Rotation (double rotation)
3. Right-Right (RR) violation → balance = −2 and right child balance ≤ 0 → Left Rotation (single rotation)
4. Right-Left (RL) violation → balance = −2 and right child balance = +1 → Right-Left Rotation (double rotation)

Most Important: Right Rotation (LL case) – Visual & Code

Before (balance factor +2 at node 10):

After Right Rotation:

Right Rotation code (on node y):

Left Rotation (RR case)

Before:

After Left Rotation:

LR & RL Cases – Double Rotations

LR case (Left-Right):

Steps:

1. Left rotate on left child (5 → 7 becomes root of left subtree)
2. Right rotate on original node (10)

Result:

RL case is symmetric: right rotate first on right child, then left rotate on original node.

AVL Tree Node with Height

Helper functions

Insert in AVL Tree (with balancing)

Why AVL Trees are still important (2025–2026 context)

Disadvantages compared to Red-Black:

• More rotations (especially during insertion/deletion)
• Slightly more complex code
• Red-Black trees usually perform better in practice (fewer rotations)

Summary – AVL Tree in one line each

• Self-balancing Binary Search Tree
• Balance factor of every node = −1, 0, or +1
• Uses rotations (LL, LR, RR, RL) to maintain balance
• Guarantees O(log n) time for search, insert, delete in worst case
• In-order traversal → sorted order
• Most important to understand rotations and balance factor
• Classic interview topic to test recursion, tree manipulation, and balancing logic

Would you like to go deeper into any part?

Very common next topics:

• Step-by-step rotation examples (LL, LR, RR, RL) with multiple cases
• AVL Tree insert dry run with balancing
• AVL vs Red-Black Tree detailed comparison
• Delete operation in AVL Tree
• Is AVL Tree still used in 2026? (real-world usage)

Just tell me which direction you want — I’ll continue in the same detailed, teacher-style with drawings and examples! 😊