Binary Tree

Hierarkisk

En hierarkisk datastruktur hvor hvert node har maksimalt to børn: venstre og højre child.

Kompleksitet

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

Beskrivelse

Et Binary Tree er en træstruktur hvor hvert node har maksimalt to børn. Dette skaber en hierarkisk organisation af data med en root node i toppen og leaf nodes i bunden uden børn. Binary trees kommer i mange varianter: Binary Search Trees (BST) hvor venstre barn er mindre og højre større, Balanced Trees som AVL og Red-Black trees der automatisk balancerer sig selv, og Complete Binary Trees hvor alle niveauer er fyldte undtagen muligvis det sidste. Binary trees er fundamentale i computer science og bruges til effektiv søgning, sortering og hierarkisk datarepræsentation. Traversering kan ske in-order, pre-order eller post-order afhængigt af anvendelsen. Binary Search Trees giver O(log n) performance for balancerede træer, men kan degradere til O(n) hvis ubalanceret.

Kode Eksempel

// JavaScript Binary Search Tree
class TreeNode {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

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

  // Indsæt værdi
  insert(value) {
    const newNode = new TreeNode(value);
    if (!this.root) {
      this.root = newNode;
      return;
    }
    let current = this.root;
    while (true) {
      if (value < current.value) {
        if (!current.left) {
          current.left = newNode;
          return;
        }
        current = current.left;
      } else {
        if (!current.right) {
          current.right = newNode;
          return;
        }
        current = current.right;
      }
    }
  }

  // Søg efter værdi
  search(value) {
    let current = this.root;
    while (current) {
      if (value === current.value) return true;
      if (value < current.value) {
        current = current.left;
      } else {
        current = current.right;
      }
    }
    return false;
  }

  // In-order traversal (sorteret output)
  inOrder(node = this.root, result = []) {
    if (node) {
      this.inOrder(node.left, result);
      result.push(node.value);
      this.inOrder(node.right, result);
    }
    return result;
  }
}

Anvendelsesområder

•Sorterede dataoversigter og range queries
•Auto-complete funktionalitet i tekstfelter
•Filsystem og directory structures
•Expression parsing i compilere
•Prioritetskøer og scheduling

Fordele

✓Effektiv søgning O(log n) når balanceret
✓Naturlig hierarkisk organisering
✓In-order traversal giver sorteret output
✓Fleksibel til mange anvendelser
✓Bedre end arrays til hyppige indsættelser

Ulemper

✗Kan blive ubalanceret (worst case O(n))
✗Kræver ekstra hukommelse til pointere
✗Mere kompleks implementering end arrays
✗Balancering kræver ekstra arbejde (AVL, Red-Black)
✗Ikke cache-venlig struktur

Eksempler fra den virkelige verden

•Organisationshierarkier (CEO → managers → medarbejdere)
•HTML DOM struktur i browsers
•Beslutnings træer i machine learning
•XML/JSON parsere
•Turnerings brackets i sportsbegivenheder

Relaterede strukturer

Binary Search TreeAVL TreeRed-Black TreeB-TreeHeap