AVL Tree

Træ

Et self-balancing binært søgetræ hvor højdeforskellen mellem venstre og højre subtræ er maksimalt 1.

Kompleksitet

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

Beskrivelse

AVL Tree er opkaldt efter opfinderne Adelson-Velsky og Landis og var det første self-balancing binary search tree der blev opfundet. I et AVL Tree holdes træet balanceret ved at sikre at balance factor (højde af venstre subtræ minus højre subtræ) for hver node er -1, 0 eller 1. Når balance factor bliver udenfor dette interval efter insertion eller deletion, anvendes rotationer for at genbalancere træet. Der findes fire typer rotationer: Left-Left (single right rotation), Right-Right (single left rotation), Left-Right (double rotation) og Right-Left (double rotation). AVL Trees garanterer O(log n) tid for search, insertion og deletion operationer fordi træet altid er perfekt balanceret. Dette gør AVL Trees ideelle til applikationer hvor lookup er meget hyppigere end insertions og deletions. Sammenlignet med Red-Black Trees er AVL Trees mere strikt balanceret, hvilket giver hurtigere searches men langsommere insertions og deletions 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; // Duplicate values not allowed
    }

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

    // Left-Left Case
    if (balance > 1 && value < node.left.value) {
      return this.rightRotate(node);
    }

    // Right-Right Case
    if (balance < -1 && value > node.right.value) {
      return this.leftRotate(node);
    }

    // Left-Right Case
    if (balance > 1 && value > node.left.value) {
      node.left = this.leftRotate(node.left);
      return this.rightRotate(node);
    }

    // Right-Left Case
    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); // Trigger rotation
tree.add(40);
tree.add(50);
console.log(tree.find(30)); // true

Anvendelsesområder

•In-memory sorting med hyppige lookups
•Ordered data med sjældne updates
•Database indexering hvor read performance er kritisk
•Auto-complete og typeahead features
•Range queries på sorteret data

Fordele

✓Garanteret O(log n) for alle operationer
✓Mere strikt balanceret end Red-Black Trees
✓Hurtigere searches end andre balanced trees
✓Opretholder sorted order
✓God cache locality pga. balance

Ulemper

✗Flere rotationer end Red-Black Trees ved insertion/deletion
✗Mere kompleks implementation
✗Ekstra memory til at gemme height information
✗Langsommere insertions end Red-Black Trees
✗Rebalancing overhead kan være betydelig

Eksempler fra den virkelige verden

•Database indexes hvor lookup er hyppig (банкsystemer)
•Sorting algorithms i Java Collections TreeMap
•In-memory caches med ordered keys
•Symbol tables i compilers
•Telefonbøger med hurtig navnesøgning

Relaterede strukturer

Red-Black TreeBinary Search TreeB-TreeSplay Tree