Course contentsShow
← Java
Lesson 1137 of 2,87026. Map ImplementationsFree lesson

Red-Black Tree Internals: Balancing Operations

How TreeMap maintains O(log n) performance through Red-Black tree rotations and rebalancing.

Red-Black Tree Internals: Balancing Operations

You'll learn how TreeMap keeps lookups, insertions, and deletions fast through automatic rebalancing.

The Challenge of Binary Search Trees

A regular binary search tree can degenerate into a linked list if you insert sorted data (1, 2, 3, 4...). This creates O(n) performance—terrible! TreeMap uses a Red-Black tree to prevent this disaster.

What Are Red-Black Trees?

Red-Black trees maintain balance by coloring each node red or black and enforcing strict rules:

  1. Every node is either red or black
  2. The root is always black
  3. Red nodes cannot have red children
  4. Every path from root to null has the same number of black nodes

These rules guarantee the tree never becomes more than twice as tall as a perfectly balanced tree, ensuring O(log n) performance.

Balancing Through Rotations

When you insert or remove a key, the tree might violate these color rules. TreeMap immediately fixes violations through two operations:

Rotations restructure the tree by pivoting nodes. Imagine a left rotation as lifting a right child to become the new parent, with the old parent becoming its left child. This changes the tree's shape without breaking the sorted order.

Recoloring flips node colors (red ↔ black) to restore rule compliance, often combined with rotations.

The Performance Guarantee

These operations happen in O(log n) time because the tree height is logarithmic. A TreeMap with 1,000,000 entries only needs about 20 comparisons maximum—far better than scanning linearly. The rebalancing itself is also O(log n), so every operation stays fast.

Key Takeaway: TreeMap maintains O(log n) performance by using Red-Black tree rotations and recoloring to automatically rebalance after every insertion or deletion, preventing the tree from becoming lopsided.