Red-Black Tree

Træ

Et self-balancing binært søgetræ hvor hver node har en farve (rød eller sort) med specifikke balanceringsregler.

Kompleksitet

Operation	Tidskompleksitet
Access	`O(log n)`
Search	`O(log n)`
Insertion	`O(log n)`
Deletion	`O(log n)`

Beskrivelse

Red-Black Tree er en af de mest anvendte self-balancing binary search trees i produktionssystemer. Hver node i træet er farvet enten rød eller sort, og træet skal opfylde fem strenge regler: 1) Hver node er enten rød eller sort, 2) Roden er altid sort, 3) Alle blade (NULL nodes) er sorte, 4) Røde nodes kan ikke have røde børn (ingen to røde nodes i træk), 5) Alle veje fra en node til dens blade indeholder samme antal sorte nodes (black height). Disse regler sikrer at træet forbliver relativt balanceret uden at være perfekt balanceret som AVL Trees. Den længste vej i træet kan maksimalt være dobbelt så lang som den korteste vej. Sammenlignet med AVL Trees kræver Red-Black Trees færre rotationer ved insertion og deletion, hvilket gør dem hurtigere til write-heavy workloads. De bruges i Linux kernel, Java TreeMap og TreeSet, C++ std::map og std::set, og mange andre kritiske systemer hvor performance og pålidelighed er vigtig.

Kode Eksempel

// JavaScript Red-Black Tree Implementation (simplified)
class RBNode {
  constructor(value, color = 'RED') {
    this.value = value;
    this.color = color; // 'RED' or 'BLACK'
    this.left = null;
    this.right = null;
    this.parent = null;
  }
}

class RedBlackTree {
  constructor() {
    this.root = null;
  }

  rotateLeft(node) {
    const rightChild = node.right;
    node.right = rightChild.left;
    
    if (rightChild.left !== null) {
      rightChild.left.parent = node;
    }
    
    rightChild.parent = node.parent;
    
    if (node.parent === null) {
      this.root = rightChild;
    } else if (node === node.parent.left) {
      node.parent.left = rightChild;
    } else {
      node.parent.right = rightChild;
    }
    
    rightChild.left = node;
    node.parent = rightChild;
  }

  rotateRight(node) {
    const leftChild = node.left;
    node.left = leftChild.right;
    
    if (leftChild.right !== null) {
      leftChild.right.parent = node;
    }
    
    leftChild.parent = node.parent;
    
    if (node.parent === null) {
      this.root = leftChild;
    } else if (node === node.parent.right) {
      node.parent.right = leftChild;
    } else {
      node.parent.left = leftChild;
    }
    
    leftChild.right = node;
    node.parent = leftChild;
  }

  insert(value) {
    const newNode = new RBNode(value, 'RED');
    
    if (this.root === null) {
      newNode.color = 'BLACK';
      this.root = newNode;
      return;
    }
    
    // Standard BST insertion
    let current = this.root;
    let parent = null;
    
    while (current !== null) {
      parent = current;
      if (value < current.value) {
        current = current.left;
      } else if (value > current.value) {
        current = current.right;
      } else {
        return; // Duplicate
      }
    }
    
    newNode.parent = parent;
    if (value < parent.value) {
      parent.left = newNode;
    } else {
      parent.right = newNode;
    }
    
    this.fixInsert(newNode);
  }

  fixInsert(node) {
    while (node.parent && node.parent.color === 'RED') {
      if (node.parent === node.parent.parent.left) {
        const uncle = node.parent.parent.right;
        
        if (uncle && uncle.color === 'RED') {
          // Case 1: Uncle is red - recolor
          node.parent.color = 'BLACK';
          uncle.color = 'BLACK';
          node.parent.parent.color = 'RED';
          node = node.parent.parent;
        } else {
          // Case 2 & 3: Uncle is black
          if (node === node.parent.right) {
            node = node.parent;
            this.rotateLeft(node);
          }
          node.parent.color = 'BLACK';
          node.parent.parent.color = 'RED';
          this.rotateRight(node.parent.parent);
        }
      } else {
        // Mirror cases
        const uncle = node.parent.parent.left;
        
        if (uncle && uncle.color === 'RED') {
          node.parent.color = 'BLACK';
          uncle.color = 'BLACK';
          node.parent.parent.color = 'RED';
          node = node.parent.parent;
        } else {
          if (node === node.parent.left) {
            node = node.parent;
            this.rotateRight(node);
          }
          node.parent.color = 'BLACK';
          node.parent.parent.color = 'RED';
          this.rotateLeft(node.parent.parent);
        }
      }
    }
    
    this.root.color = 'BLACK';
  }

  search(value) {
    let current = this.root;
    while (current !== null) {
      if (value === current.value) return true;
      if (value < current.value) {
        current = current.left;
      } else {
        current = current.right;
      }
    }
    return false;
  }
}

// Brug
const tree = new RedBlackTree();
tree.insert(10);
tree.insert(20);
tree.insert(30);
tree.insert(15);
console.log(tree.search(15)); // true

Anvendelsesområder

•Standard library implementations (map, set)
•Database indexing med frequent insertions
•Scheduler i operating systems
•Process prioritering i kernels
•Memory management allocators

Fordele

✓Færre rotationer end AVL Trees (hurtigere insertions)
✓Garanteret O(log n) operations
✓Bedre til write-heavy workloads
✓Anvendt i mange production systems
✓God balance mellem performance og kompleksitet

Ulemper

✗Lidt langsommere searches end AVL Trees
✗Mere kompleks implementation end basic BST
✗Color information kræver ekstra memory
✗Sværere at forstå og debugge
✗Ikke så strikt balanceret som AVL Trees

Eksempler fra den virkelige verden

•Linux kernel scheduler (Completely Fair Scheduler)
•Java TreeMap og TreeSet implementation
•C++ STL map og set containers
•MySQL InnoDB index structures
•Python sorted containers i visse biblioteker

Relaterede strukturer

AVL TreeBinary Search TreeB-TreeSplay Tree