Ein Binärbaum ist eine Baum-Datenstruktur, bei der jeder Knoten höchstens zwei Kindknoten besitzt. Man unterscheidet das linke und das rechte Kind. Diese einfache Beschränkung macht Binärbäume besonders gut speicherbar und effizient durchsuchbar.
Aufbau eines Binärbaums
- Wurzel: Der oberste Knoten, mit dem der Baum beginnt.
- Kinder: Jeder Knoten kann ein linkes und ein rechtes Kind haben — oder keins, dann heißt er Blatt.
- Tiefe: Die Anzahl der Ebenen unter der Wurzel. In einem ausbalancierten Binärbaum mit n Knoten beträgt die Tiefe etwa log₂(n) — daraus entsteht die schnelle Zugriffszeit.
Ist jeder Knoten außer der letzten Ebene voll besetzt und die letzte Ebene von links gefüllt, spricht man von einem vollständigen Binärbaum. Ein balancierter Binärbaum hält linke und rechte Teilbäume in ähnlicher Höhe, damit kein Ast entartet.
Besondere Formen
- Binärer Suchbaum (BST): Im linken Teilbaum stehen kleinere, im rechten Teilbaum größere Schlüssel als im Knoten. Dadurch findet man Daten in O(log n) — ähnlich wie bei einem Index in einer Datenbank.
- Heap: Ein fast vollständiger Binärbaum mit fester Ordnung zwischen Eltern- und Kindknoten. Er dient als Prioritätswarteschlange und treibt Heap Sort an.
Speicherung
Ein Binärbaum lässt sich über zwei Zeiger pro Knoten darstellen — ähnlich wie bei einer verketteten Liste, nur mit zwei Verweisen statt einem. Für vollständige Binärbäume genügt sogar ein Array ohne Zeiger: Das Kind von Position i liegt auf 2i und 2i+1.
Anwendungen
- Suchbäume für schnelles Einfügen, Löschen und Finden von Schlüsseln
- Ausdrucksbäume in Compilern: Operatoren als Knoten, Operanden als Blätter
- Huffman-Kodierung zur Datenkompression
- Entscheidungsbäume im maschinellen Lernen
Ein Binärbaum wird typischerweise mit Rekursion aufgebaut und durchlaufen. Die Traversierung besucht dabei jeden Knoten systematisch genau einmal — etwa um die Elemente eines Suchbaums sortiert auszugeben. Als Spezialfall eines Baums hängt der Binärbaum eng mit der Graph-Datenstruktur zusammen: Jeder Baum ist ein kreisfreier Graph.