Binært Træ

Hierarkisk

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

Foto: Niall Smith / Unsplash

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