Balanced Trees Concept (Height Balancing)

In a standard Binary Search Tree (BST), search, insertion, and deletion run in O(h) time, where h is the height of the tree.

• In a balanced tree with n nodes: h = ≈ log₂(n) → O(log n) speed!
• But what happens if you insert sorted data: 1, 2, 3, 4, 5?

The Degenerate Tree Problem (BST Collapse)

Inserting sorted values into an unaugmented BST collapses the tree into a linear linked list:

Copy code[ 1 ]
   \
   [ 2 ]
      \
      [ 3 ]
         \
         [ 4 ]
            \
            [ 5 ]

• Height h = n.
• Search time degrades from O(log n) down to O(n)!
• All benefits of using a tree are destroyed.

What is a Balanced Tree?

A tree is Height-Balanced if the heights of the left and right subtrees of any node differ by at most 1 (or a small constant factor), guaranteeing that h = O(log n) at all times.

Tree Rotations: The Rebalancing Mechanism

Balanced trees maintain height invariant by performing local rotations in O(1) time upon insertion or deletion:

Right Rotation (LL Rotation)

Used when the left subtree is too tall:

Copy code       [ Y ]                      [ X ]
      /     \                    /     \
    [ X ]   [ C ]   ====>      [ A ]   [ Y ]
   /     \                            /     \
 [ A ]   [ B ]                       [ B ]   [ C ]

Copy codefun rotateRight(y: Node): Node {
    val x = y.left!!
    val b = x.right
    x.right = y
    y.left = b
    return x // x is new root of subtree!
}

Production Balanced Tree Implementations

1. AVL Trees (Adelson-Velsky and Landis)

• Strictly Balanced: Balance factor |height(L) - height(R)| ≤ 1.
• Provides the fastest lookup times because height is strictly minimal.
• Slightly slower insertions and deletions due to frequent rebalancing rotations.
• Best for: Read-heavy workloads (lookups >> writes).

2. Red-Black Trees

• Relaxed Balance: Each node is colored Red or Black with specific balancing invariants (e.g., no two red nodes in a row).
• Guarantees the longest path is at most 2 × the shortest path.
• Requires fewer rotations during insertions and deletions.
• Best for: General-purpose systems (Java's TreeMap, TreeSet, Linux kernel CFS scheduler, C++ std::map).

Summary

• Unbalanced BSTs degenerate into O(n) linked lists under sorted input.
• Balanced Trees perform O(1) rotations to guarantee h = O(log n) height.
• AVL Trees offer strictly optimal search; Red-Black Trees balance write and read performance for production libraries.