Self-Balancing & Advanced Trees

Standard Binary Search Trees suffer from a catastrophic worst-case: when elements are inserted in sorted or near-sorted order, the tree degenerates into a linear chain with height O(n), destroying O(log n) performance. Self-balancing trees restore height balance after insertions and deletions through tree rotations.

1. AVL Trees (Strict Balance)Copy Anchor Link

Invented by Adelson-Velsky and Landis (1962), an AVL Tree is a self-balancing binary search tree where the height difference (the Balance Factor) of the left and right subtrees of any node cannot exceed 1.

Balance Factor (BF) = height(left) - height(right)

Valid balance factor values are strictly -1, 0, or +1.

If BF > 1 or BF < -1, the tree is rebalanced via one of four rotation operations:

The Four Rotation MechanicsCopy Anchor Link

      z (BF = +2)               y
     /                         / \
    y           ===>          x   z
   /
  x

private TreeNode rightRotate(TreeNode z) {
    TreeNode y = z.left;
    TreeNode T3 = y.right;

    // Perform rotation
    y.right = z;
    z.left = T3;

    return y; // New root of subtree
}

2. Red-Black Trees (Industrial Standard)Copy Anchor Link

A Red-Black Tree relaxes AVL's strict height balance to minimize rotation overhead during frequent insertions and deletions. It guarantees that no root-to-leaf path is more than twice as long as any other path, keeping height bounded by 2 * log2(n + 1).

The 5 Red-Black InvariantsCopy Anchor Link

Where Java Uses Red-Black TreesCopy Anchor Link

Because Red-Black trees require at most 2 rotations for an insertion and at most 3 rotations for a deletion, Java utilizes them for its primary sorted collections:

• java.util.TreeMap: Red-black tree key-value mapping.
• java.util.TreeSet: Red-black tree unique sorted set (backed by TreeMap).
• java.util.HashMap: Bins that accumulate 8 or more colliding entries in tables of capacity 64 or greater treeify into Red-Black TreeNode buckets, bounding worst-case collision lookup at O(log n).

AVL vs Red-Black Tree ComparisonCopy Anchor Link

3. Trie (Prefix Tree)Copy Anchor Link

A Trie (pronounced "try") is an n-ary tree used for storing and searching strings where all descendants of a node share a common string prefix:

Java Trie ImplementationCopy Anchor Link

public class Trie {

    private static class TrieNode {
        TrieNode[] children = new TrieNode[26];
        boolean isEndOfWord = false;
    }

    private final TrieNode root = new TrieNode();

    // Inserts word into trie: O(L) time where L is word length
    public void insert(String word) {
        TrieNode curr = root;
        for (char ch : word.toCharArray()) {
            int idx = ch - 'a';
            if (curr.children[idx] == null) {
                curr.children[idx] = new TrieNode();
            }
            curr = curr.children[idx];
        }
        curr.isEndOfWord = true;
    }

    // Returns true if word is in trie: O(L) time
    public boolean search(String word) {
        TrieNode node = findNode(word);
        return node != null && node.isEndOfWord;
    }

    // Returns true if there is any word starting with prefix: O(L) time
    public boolean startsWith(String prefix) {
        return findNode(prefix) != null;
    }

    private TrieNode findNode(String str) {
        TrieNode curr = root;
        for (char ch : str.toCharArray()) {
            int idx = ch - 'a';
            if (curr.children[idx] == null) return null;
            curr = curr.children[idx];
        }
        return curr;
    }
}