Balanced Trees (AVL/RB)

As discussed in the BST module, if you insert sorted data into a standard Binary Search Tree (e.g., 1, 2, 3, 4, 5), the tree degrades into a Linked List. The height becomes $O(N)$, completely destroying the $O(\log N)$ performance benefits.

Balanced Trees solve this problem. They are self-adjusting BSTs that automatically reorganize themselves during insertions and deletions to guarantee that the height of the tree remains $O(\log N)$.

How do they balance? (Tree Rotations)

When a node is inserted, the tree checks if the height difference between the left and right subtrees violates the balancing rules. If it does, the tree performs a structural Rotation to fix the imbalance without breaking the BST properties.

A Right Rotation lifts the left child up to become the new root, pulling the old root down to become the new right child.

---

1. AVL Trees

Named after Adelson-Velsky and Landis, an AVL tree is a strictly balanced BST. It maintains a height variable on every node.

The AVL Property: For any node, the difference in height between its left subtree and its right subtree (the Balance Factor) can be at most 1 or -1. If it reaches 2 or -2, rotations are triggered immediately.

• Pros: Because it is so strictly balanced, it provides incredibly fast $O(\log N)$ lookups.
• Cons: It performs many rotations to maintain that strict balance, making insertions and deletions slightly slower.

---

2. Red-Black Trees

A Red-Black Tree uses a coloring mechanism (Red or Black) on nodes instead of maintaining an exact numerical height. It follows a complex set of rules (e.g., the root is always Black, Red nodes cannot have Red children, every path to a leaf has the same number of Black nodes).

• Pros: It is a loosely balanced tree. It allows a path to be up to twice as long as the shortest path. Because it is less strict, it requires far fewer rotations during insertions and deletions than an AVL tree.
• Cons: Lookups can technically be slightly slower than AVL trees (though still bounded to $O(\log N)$).

[!NOTE] Red-Black trees are extremely popular in system architecture. The std::map in C++, the TreeMap in Java, and the Completely Fair Scheduler (CFS) in the Linux kernel are all implemented using Red-Black Trees!

Time Complexity

Both AVL and Red-Black Trees guarantee $O(\log N)$ for all operations, solving the fatal flaw of the standard BST.