Red-Black Trees

Introduction

Red-Black Trees are a type of self-balancing binary search tree (BST) that maintains balance through a set of properties. They were invented by Rudolf Bayer in his Ph.D. thesis in 1972 and later modified by Leo Guibas and Robert Sedgewick. Red-Black Trees ensure that the longest path from the root to any leaf is no more than twice as long as the shortest path, which guarantees O(log n) time complexity for search, insert, and delete operations.

Properties of Red-Black Trees

A Red-Black Tree has the following properties:

1. Every node is either red or black.
2. The root is always black.
3. All leaves (NIL nodes) are black.
4. If a node is red, then both its children are black. This property ensures that no two red nodes can be adjacent.
5. For each node, all simple paths from the node to descendant NIL nodes have the same number of black nodes. This property, known as the "black-height" or "black depth," ensures balance.

These properties collectively ensure that the tree remains approximately balanced during insertions and deletions.

Node Structure

Each node in a Red-Black Tree has the following attributes:

• key: The value stored in the node.
• color: The color of the node, either red or black.
• left, right: Pointers to the left and right children.
• parent: A pointer to the parent node.

Here is a simple implementation of a Red-Black Tree node in JavaScript:

class Node {
  constructor(key) {
    this.key = key;
    this.color = 'red'; // New nodes are always red
    this.left = null;
    this.right = null;
    this.parent = null;
  }
}

Basic Operations

Insertion

Inserting a node into a Red-Black Tree involves the following steps:

1. Standard BST Insertion: Insert the node as you would in a regular binary search tree.
2. Recolor and Rotate: Adjust the colors of nodes and perform rotations to maintain the Red-Black properties.

Here is an example of how to insert a node into a Red-Black Tree:

class RedBlackTree {
  constructor() {
    this.NIL = new Node(null);
    this.NIL.color = 'black';
    this.root = this.NIL;
  }

  leftRotate(x) {
    const y = x.right;
    x.right = y.left;
    if (y.left !== this.NIL) {
      y.left.parent = x;
    }
    y.parent = x.parent;
    if (x.parent === null) {
      this.root = y;
    } else if (x === x.parent.left) {
      x.parent.left = y;
    } else {
      x.parent.right = y;
    }
    y.left = x;
    x.parent = y;
  }

  rightRotate(y) {
    const x = y.left;
    y.left = x.right;
    if (x.right !== this.NIL) {
      x.right.parent = y;
    }
    x.parent = y.parent;
    if (y.parent === null) {
      this.root = x;
    } else if (y === y.parent.right) {
      y.parent.right = x;
    } else {
      y.parent.left = x;
    }
    x.right = y;
    y.parent = x;
  }

  insert(key) {
    const z = new Node(key);
    let y = null;
    let x = this.root;

    while (x !== this.NIL) {
      y = x;
      if (z.key < x.key) {
        x = x.left;
      } else {
        x = x.right;
      }
    }

    z.parent = y;
    if (y === null) {
      this.root = z;
    } else if (z.key < y.key) {
      y.left = z;
    } else {
      y.right = z;
    }

    z.left = this.NIL;
    z.right = this.NIL;
    z.color = 'red';

    this.insertFixup(z);
  }

  insertFixup(z) {
    while (z.parent.color === 'red') {
      if (z.parent === z.parent.parent.left) {
        const y = z.parent.parent.right;
        if (y.color === 'red') {
          z.parent.color = 'black';
          y.color = 'black';
          z.parent.parent.color = 'red';
          z = z.parent.parent;
        } else {
          if (z === z.parent.right) {
            z = z.parent;
            this.leftRotate(z);
          }
          z.parent.color = 'black';
          z.parent.parent.color = 'red';
          this.rightRotate(z.parent.parent);
        }
      } else {
        const y = z.parent.parent.left;
        if (y.color === 'red') {
          z.parent.color = 'black';
          y.color = 'black';
          z.parent.parent.color = 'red';
          z = z.parent.parent;
        } else {
          if (z === z.parent.left) {
            z = z.parent;
            this.rightRotate(z);
          }
          z.parent.color = 'black';
          z.parent.parent.color = 'red';
          this.leftRotate(z.parent.parent);
        }
      }
    }
    this.root.color = 'black';
  }
}

Deletion

Deleting a node from a Red-Black Tree is more complex than in a standard BST due to the need to maintain the properties. The deletion process involves:

1. Standard BST Deletion: Remove the node as you would in a regular binary search tree.
2. Recolor and Rotate: Adjust the colors of nodes and perform rotations to maintain the Red-Black properties.

Here is an example of how to delete a node from a Red-Black Tree:

class RedBlackTree {
  // ... (previous methods)

  transplant(u, v) {
    if (u.parent === null) {
      this.root = v;
    } else if (u === u.parent.left) {
      u.parent.left = v;
    } else {
      u.parent.right = v;
    }
    if (v !== null) {
      v.parent = u.parent;
    }
  }

  deleteNode(z) {
    let y = z;
    let x;
    let originalColor = y.color;

    if (z.left === this.NIL) {
      x = z.right;
      this.transplant(z, z.right);
    } else if (z.right === this.NIL) {
      x = z.left;
      this.transplant(z, z.left);
    } else {
      y = this.treeMinimum(z.right);
      originalColor = y.color;
      x = y.right;
      if (y.parent === z) {
        x.parent = y;
      } else {
        this.transplant(y, y.right);
        y.right = z.right;
        y.right.parent = y;
      }
      this.transplant(z, y);
      y.left = z.left;
      y.left.parent = y;
      y.color = z.color;
    }

    if (originalColor === 'black') {
      this.deleteFixup(x);
    }
  }

  deleteFixup(x) {
    while (x !== this.root && x.color === 'black') {
      if (x === x.parent.left) {
        let w = x.parent.right;
        if (w.color === 'red') {
          w.color = 'black';
          x.parent.color = 'red';
          this.leftRotate(x.parent);
          w = x.parent.right;
        }
        if (w.left.color === 'black' && w.right.color === 'black') {
          w.color = 'red';
          x = x.parent;
        } else {
          if (w.right.color === 'black') {
            w.left.color = 'black';
            w.color = 'red';
            this.rightRotate(w);
            w = x.parent.right;
          }
          w.color = x.parent.color;
          x.parent.color = 'black';
          w.right.color = 'black';
          this.leftRotate(x.parent);
          x = this.root;
        }
      } else {
        let w = x.parent.left;
        if (w.color === 'red') {
          w.color = 'black';
          x.parent.color = 'red';
          this.rightRotate(x.parent);
          w = x.parent.left;
        }
        if (w.right.color === 'black' && w.left.color === 'black') {
          w.color = 'red';
          x = x.parent;
        } else {
          if (w.left.color === 'black') {
            w.right.color = 'black';
            w.color = 'red';
            this.leftRotate(w);
            w = x.parent.left;
          }
          w.color = x.parent.color;
          x.parent.color = 'black';
          w.left.color = 'black';
          this.rightRotate(x.parent);
          x = this.root;
        }
      }
    }
    x.color = 'black';
  }

  treeMinimum(node) {
    while (node.left !== this.NIL) {
      node = node.left;
    }
    return node;
  }
}

Best Practices

1. Always Start with a Red Node: New nodes are always inserted as red to simplify the insertion fixup process.
2. Maintain Black Height: Ensure that all paths from any node to its descendant NIL nodes have the same number of black nodes.
3. Use Sentinel Nodes (NIL): Use sentinel nodes to represent NIL leaves, simplifying boundary conditions and rotations.

Conclusion

Red-Black Trees are a powerful data structure for maintaining balanced binary search trees. Their properties ensure that operations like insertion, deletion, and search remain efficient with O(log n) time complexity. By understanding the properties and implementing the necessary methods, you can effectively use Red-Black Trees in various applications where dynamic balancing is required.

Further Reading

• "Introduction to Algorithms" by Cormen, Leiserson, Rivest, and Stein.
• "Algorithms (4th Edition)" by Robert Sedgewick and Kevin Wayne.