Rød-sort-træ

Træ

Et selvbalancerende 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

Rød-sort-træet er et af de mest anvendte selvbalancerende binære søgetræer 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-noder) er sorte 4) Røde noder kan ikke have røde børn (ingen to røde noder i træk) 5) Alle veje fra en node til dens blade indeholder samme antal sorte noder (sort højde) Disse regler sikrer at træet forbliver relativt balanceret uden at være perfekt balanceret som AVL-træer. Den længste vej i træet kan maksimalt være dobbelt så lang som den korteste vej. Sammenlignet med AVL-træer kræver rød-sort-træer færre rotationer ved indsættelse og sletning, hvilket gør dem hurtigere til skrive-tunge arbejdsbyrder. De bruges i Linux-kernen, Java TreeMap og TreeSet, C++ std::map og std::set, og mange andre kritiske systemer hvor ydeevne og pålidelighed er vigtig.

Kode Eksempel

// JavaScript Red-Black Tree Implementation (forenklet)
class RBNode {
  constructor(value, color = 'RED') {
    this.value = value;
    this.color = color; // 'RED' eller '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-indsættelse
    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; // Duplikat
      }
    }
    
    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') {
          // Tilfælde 1: Onkel er rød - omfarv
          node.parent.color = 'BLACK';
          uncle.color = 'BLACK';
          node.parent.parent.color = 'RED';
          node = node.parent.parent;
        } else {
          // Tilfælde 2 & 3: Onkel er sort
          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 {
        // Spejltilfælde
        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

•Standardbiblioteksimplementeringer (map, set)
•Databaseindeksering med hyppige indsættelser
•Planlægning i styresystemer
•Procesprioritetering i kerner
•Hukommelsesallokatorer

Fordele

✓Færre rotationer end AVL-træer (hurtigere indsættelser)
✓Garanteret O(log n) operationer
✓Bedre til skrive-tunge arbejdsbyrder
✓Anvendt i mange produktionssystemer
✓God balance mellem ydeevne og kompleksitet

Ulemper

✗Lidt langsommere søgninger end AVL-træer
✗Mere kompleks implementering end basalt BST
✗Farveinformation kræver ekstra hukommelse
✗Sværere at forstå og fejlfinde
✗Ikke så strikt balanceret som AVL-træer

Eksempler fra den virkelige verden

•Linux-kernens planlægger (Completely Fair Scheduler)
•Java TreeMap og TreeSet-implementering
•C++ STL map og set-containere
•MySQL InnoDB-indeksstrukturer
•Python sorterede containere i visse biblioteker

Relaterede strukturer

AVL TreeBinary Search TreeB-TreeSplay Tree