Balanced Trees – AVL Trees -

🌟 Balanced Trees – AVL Trees

Let’s start with a simple question:
What happens if a Binary Search Tree (BST) grows unevenly — with all nodes leaning to one side?

It becomes slow.

Imagine climbing a ladder that’s almost flat on the ground — you’d take forever to reach the top!
That’s what happens when a BST becomes unbalanced.

To fix that problem, we use something called a Balanced Tree, and one of the most famous types is the AVL Tree.

🌱 The Problem with Normal BSTs

A Binary Search Tree works great when it’s balanced, meaning both left and right sides have roughly the same number of nodes.

But if you keep inserting numbers in sorted order, like 10, 20, 30, 40, 50…
you’ll end up with something like this:

That’s no longer a tree — it’s a chain!
Now searching for 50 means checking every single node — just like a linked list.
So instead of O(log n), it becomes O(n). Ouch 😬

🌳 Enter AVL Trees

To prevent this, we use AVL Trees — short for Adelson-Velsky and Landis Trees,
named after the two computer scientists who invented them in 1962.

An AVL Tree is a self-balancing binary search tree.

That means every time you insert or delete a node,
the tree automatically adjusts itself to stay balanced. 🌿

🧠 Balance Factor – The Key Idea

To know if the tree is balanced or not, AVL Trees use a simple number called the Balance Factor (BF).

For any node:
[
\text{Balance Factor} = \text{Height of Left Subtree} – \text{Height of Right Subtree}
]

Now:

If BF = 0 → perfectly balanced 🌸
If BF = +1 or -1 → still okay, slightly tilted but fine 😊
If BF = +2 or -2 → imbalance detected! ⚠️

When that happens, the tree performs rotations to bring things back into shape.

🌿 Rotations — The Balancing Trick

Think of rotations like gently rotating a see-saw to make both sides even again.
There are four types of rotations in AVL Trees:

Right Rotation (LL Case) – when the left side is too heavy
Left Rotation (RR Case) – when the right side is too heavy
Left-Right Rotation (LR Case) – left child is heavy on its right
Right-Left Rotation (RL Case) – right child is heavy on its left

These rotations re-arrange nodes without breaking BST rules.

🌲 Diagram: Simple Right Rotation (LL Case)

Let’s say you inserted nodes 30, 20, 10 (in this order).

Before balancing:

The left side is too heavy (BF = +2 at node 30).

Now, perform a right rotation around 30:

       20
      /  \
    10    30

Ta-da! 🎉
The tree is balanced again.

🌳 Diagram: Simple Left Rotation (RR Case)

Now suppose you inserted 10, 20, 30.

Before balancing:

The right side is too heavy (BF = -2 at node 10).
Perform a left rotation around 10:

     20
    /  \
  10    30

Balanced again! 🌈

🔍 Searching in an AVL Tree

Now that the tree stays balanced automatically,
searching works just like in a regular BST — but faster on average.

You start at the root, and:

If the value is smaller → go left.
If larger → go right.
If equal → found! 🎯

The beauty is that since the tree’s height is always around log₂(n),
the search time is always fast — even for large datasets.

💡 Real-Life Analogy

Imagine a bookshelf that automatically rearranges itself every time you add a new book —
so that the shelves are always evenly filled.

That’s what an AVL Tree does —
it “rebalances” itself automatically so that no side becomes too tall or too empty.

⚙️ Time Complexity

Operation	Average Case	Worst Case
Search	O(log n)	O(log n)
Insertion	O(log n)	O(log n)
Deletion	O(log n)	O(log n)

No matter how many elements you add,
the tree will never become a long chain again. 🚀

🌼 Advantages

✅ Always stays balanced.
✅ Fast searching, insertion, and deletion.
✅ Great for data that changes frequently.

🍂 Limitations

❌ Rotations make insertions and deletions more complex.
❌ Not as simple to implement as a plain BST.
❌ Slightly more memory needed to store balance factors.