Eventually Bitwise

AVL & Red-Black Trees

Overview

AVL and Red-Black trees are Self-Balancing Binary Search Trees (BSTs). In a standard BST, if elements are inserted in sorted order, the tree becomes a linked list (degenerate), leading to $O(n)$ search time. Self-balancing trees ensure the height remains $O(\log n)$ by rotating nodes during insertion and deletion.

Core Concepts

  • AVL Trees:
    • Strict Balancing: The height difference between the left and right subtrees (the Balance Factor) of any node can be at most 1.
    • Rotations: Uses Single (LL, RR) and Double (LR, RL) rotations to fix imbalances.
    • Performance: Faster lookups than Red-Black trees due to stricter balancing, but slower insertions/deletions due to more rotations.
  • Red-Black Trees:
    • Approximate Balancing: Uses a coloring scheme (Red or Black) and a set of rules to ensure the tree is “roughly” balanced.
    • Rules:
      • Every node is either red or black.
      • The root is always black.
      • Red nodes cannot have red children (no two consecutive reds).
      • Every path from a node to its descendant NULL nodes must contain the same number of black nodes.
    • Performance: Faster insertions and deletions than AVL trees. Used in many standard libraries (e.g., Java’s TreeMap, C++’s std::map).

Code Examples

// Conceptual AVL rotation
function rotateRight(y: Node): Node {
    let x = y.left;
    let T2 = x.right;

    // Perform rotation
    x.right = y;
    y.left = T2;

    // Update heights
    y.height = Math.max(getHeight(y.left), getHeight(y.right)) + 1;
    x.height = Math.max(getHeight(x.left), getHeight(x.right)) + 1;

    return x; // New root
}

Use Cases

  • Databases: Indexing large datasets where search, insertion, and deletion must all stay $O(\log n)$.
  • Memory Maps: Implementing associative arrays/maps in standard libraries.
  • Virtual Memory: Managing memory regions in OS kernels.

Gotchas

  • Implementation Complexity: Implementing these trees from scratch is error-prone due to the many rotation and recoloring cases.
  • Overhead: For small datasets, a simple BST or even an array might be faster due to lower constant overhead.

Related Notes

, ,