Eventually Bitwise

AVL and Red-Black Trees

Overview

AVL and Red-Black Trees are types of 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)$ time complexity for operations. Self-balancing trees use rotations and recoloring to maintain a height of $O(\log n)$, ensuring efficient search, insertion, and deletion.

Core Concepts

  • Balance Factor: The height difference between the left and right subtrees of a node.
  • AVL Trees (Adelson-Velsky and Landis):
    • Strict Balance: The balance factor of every node must be $-1$, $0$, or $+1$.
    • Rotations: Uses single (Left, Right) and double (Left-Right, Right-Left) rotations to rebalance after insertions or deletions.
    • Trade-off: Faster lookups than Red-Black trees due to stricter balancing, but slower insertions/deletions due to more frequent rotations.
  • Red-Black Trees:
    • Relaxed Balance: Uses a coloring scheme (Red or Black) to ensure the path from the root to the furthest leaf is no more than twice as long as the path to the nearest leaf.
    • Properties:
      • 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.
    • Trade-off: Faster insertions and deletions than AVL trees because they require fewer rotations.
  • Complexity: Both guarantee $O(\log n)$ for search, insert, and delete.

Code Examples

// Conceptual representation of a rotation in a balanced tree
class Node {
    value: number;
    left: Node | null = null;
    right: Node | null = null;
    height: number = 1; // Used for AVL balance factor

    constructor(val: number) { this.value = val; }
}

function rotateRight(y: Node): Node {
    let x = y.left!;
    let T2 = x.right;

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

    // Update heights (Simplified)
    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
}

function getHeight(node: Node | null): number {
    return node ? node.height : 0;
}

Use Cases

  • Databases: B-Trees (a generalization of balanced trees) are used for indexing.
  • Language Runtimes: The std::map in C++ and TreeMap in Java are typically implemented using Red-Black Trees.
  • Filesystems: Used in some filesystem implementations to manage block allocation.

Gotchas

  • Implementation Complexity: Implementing these trees from scratch is error-prone due to the numerous rotation cases.
  • Overkill for Small Data: For small datasets, the overhead of balancing may outweigh the benefits compared to a simple BST or Hash Table.

Related Notes

, ,