Binært Træ

Hierarkisk

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

Kompleksitet

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

Beskrivelse

Et binært træ er en træstruktur hvor hver node har maksimalt to børn. Dette skaber en hierarkisk organisation af data med en rodnode i toppen og bladnoder i bunden uden børn. Binære træer kommer i mange varianter: Binære søgetræer (BST) hvor venstre barn er mindre og højre større, balancerede træer som AVL og Red-Black trees der automatisk balancerer sig selv, og komplette binære træer hvor alle niveauer er fyldte undtagen muligvis det sidste. Binære træer er fundamentale i datalogi 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. Binære søgetræer giver O(log n) ydeevne 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 intervalforespørgsler
•Autofuldførelse i tekstfelter
•Filsystemer og mappestrukturer
•Udtryksfortolkning i compilere
•Prioritetskøer og planlægning

Fordele

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

Ulemper

✗Kan blive ubalanceret (værste tilfælde 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 (direktør → ledere → medarbejdere)
•HTML DOM-struktur i browsere
•Beslutningstræer i maskinlæring
•XML/JSON-parsere
•Turneringsoversigter i sportsbegivenheder

Relaterede strukturer

Binary Search TreeAVL TreeRed-Black TreeB-TreeHeap