AVL-træ

Træ

Et selvbalancerende binært søgetræ hvor højdeforskellen mellem venstre og højre undertræ er maksimalt 1.

Foto: Niall Smith / Unsplash

Kompleksitet

Operation	Tidskompleksitet
access	`O(log n)`
search	`O(log n)`
insertion	`O(log n)`
deletion	`O(log n)`

Beskrivelse

AVL-træet er opkaldt efter opfinderne Adelson-Velsky og Landis og var det første selvbalancerende binære søgetræ der blev opfundet. I et AVL-træ holdes træet balanceret ved at sikre at balancefaktoren (højde af venstre undertræ minus højre undertræ) for hver node er -1, 0 eller 1. Når balancefaktoren bliver udenfor dette interval efter indsættelse eller sletning, anvendes rotationer for at genbalancere træet. Der findes fire typer rotationer: Venstre-Venstre (enkelt højrerotation), Højre-Højre (enkelt venstrerotation), Venstre-Højre (dobbelt rotation) og Højre-Venstre (dobbelt rotation). AVL-træer garanterer O(log n) tid for søgning, indsættelse og sletning fordi træet altid er perfekt balanceret. Dette gør AVL-træer ideelle til applikationer hvor opslag er meget hyppigere end indsættelser og sletninger. Sammenlignet med Red-Black-træer er AVL-træer mere strikt balancerede, hvilket giver hurtigere søgninger men langsommere indsættelser og sletninger pga. flere rotationer.

Kode Eksempel

// JavaScript AVL Tree Implementation
class AVLNode {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
    this.height = 1;
  }
}

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

  height(node) {
    return node ? node.height : 0;
  }

  getBalance(node) {
    return node ? this.height(node.left) - this.height(node.right) : 0;
  }

  rightRotate(y) {
    const x = y.left;
    const T2 = x.right;
    x.right = y;
    y.left = T2;
    y.height = Math.max(this.height(y.left), this.height(y.right)) + 1;
    x.height = Math.max(this.height(x.left), this.height(x.right)) + 1;
    return x;
  }

  leftRotate(x) {
    const y = x.right;
    const T2 = y.left;
    y.left = x;
    x.right = T2;
    x.height = Math.max(this.height(x.left), this.height(x.right)) + 1;
    y.height = Math.max(this.height(y.left), this.height(y.right)) + 1;
    return y;
  }

  insert(node, value) {
    if (!node) return new AVLNode(value);

    if (value < node.value) {
      node.left = this.insert(node.left, value);
    } else if (value > node.value) {
      node.right = this.insert(node.right, value);
    } else {
      return node; // Duplikater ikke tilladt
    }

    node.height = 1 + Math.max(this.height(node.left), this.height(node.right));
    const balance = this.getBalance(node);

    // Venstre-Venstre tilfælde
    if (balance > 1 && value < node.left.value) {
      return this.rightRotate(node);
    }

    // Højre-Højre tilfælde
    if (balance < -1 && value > node.right.value) {
      return this.leftRotate(node);
    }

    // Venstre-Højre tilfælde
    if (balance > 1 && value > node.left.value) {
      node.left = this.leftRotate(node.left);
      return this.rightRotate(node);
    }

    // Højre-Venstre tilfælde
    if (balance < -1 && value < node.right.value) {
      node.right = this.rightRotate(node.right);
      return this.leftRotate(node);
    }

    return node;
  }

  add(value) {
    this.root = this.insert(this.root, value);
  }

  search(node, value) {
    if (!node) return false;
    if (value === node.value) return true;
    if (value < node.value) return this.search(node.left, value);
    return this.search(node.right, value);
  }

  find(value) {
    return this.search(this.root, value);
  }
}

// Brug
const tree = new AVLTree();
tree.add(10);
tree.add(20);
tree.add(30); // Udløser rotation
tree.add(40);
tree.add(50);
console.log(tree.find(30)); // true

Anvendelsesområder

-Hukommelsesbaseret sortering med hyppige opslag
-Ordnede data med sjældne opdateringer
-Databaseindeksering hvor læseydelse er kritisk
-Autofuldførelse og typeahead-funktioner
-Intervalforespørgsler på sorterede data

Fordele

+Garanteret O(log n) for alle operationer
+Mere strikt balanceret end Red-Black-træer
+Hurtigere søgninger end andre balancerede træer
+Opretholder sorteret rækkefølge
+God cache-lokalitet pga. balance

Ulemper

-Flere rotationer end Red-Black-træer ved indsættelse/sletning
-Mere kompleks implementering
-Ekstra hukommelse til at gemme højdeinformation
-Langsommere indsættelser end Red-Black-træer
-Rebalanceringsomkostninger kan være betydelige

Eksempler fra den virkelige verden

-Databaseindekser hvor opslag er hyppige (banksystemer)
-Sorteringsalgoritmer i Java Collections TreeMap
-Hukommelsesbaserede caches med ordnede nøgler
-Symboltabeller i compilere
-Telefonbøger med hurtig navnesøgning

Relaterede strukturer

Red-Black TreeBinary Search TreeB-TreeSplay Tree