Binärer Suchbaum: Sortierte Daten schnell suchen, einfügen und löschen

Binärer Suchbaum (Binary Search Tree, BST) ist ein Binärbaum mit einer Sortierregel: Für jeden Knoten enthält der linke Teilbaum nur kleinere und der rechte Teilbaum nur größere Schlüssel (bei gleichen Werten je nach Variante links oder rechts). Dadurch lassen sich Daten in logarithmischer Zeit durchsuchen.

Wofür man ihn braucht

  • Symboltabellen und Wörterbücher: Schlüssel schnell nachschlagen und aktualisieren.
  • Sortierte Mengen: Elemente geordnet speichern, Minimum/Maximum in O(log n) finden.
  • Autovervollständigung: Präfix-Suchen über gespeicherte Wörter.
  • Datenbank-Interna: Viele Indexstrukturen bauen auf der gleichen Idee auf (balancierte Bäume).

So funktioniert die Suche

1. Beim Wurzelknoten beginnen
2. Gesuchten Wert mit dem aktuellen Knoten vergleichen
3. Gleich: gefunden
4. Kleiner: in den linken Teilbaum gehen
5. Größer: in den rechten Teilbaum gehen
6. Kein Knoten mehr vorhanden: Wert existiert nicht

Jeder Vergleich halbiert den verbleibenden Suchraum — daher die Laufzeit O(h), wobei h die Höhe des Baums ist. In einem ausgewogenen Baum mit n Elementen gilt h ≈ log n, die Suche braucht also O(log n). Werden Elemente jedoch in sortierter Reihenfolge eingefügt, entartet der Baum zu einer Kette und die Suche kostet O(n) — deshalb gibt es balancierte Varianten wie den AVL-Baum oder Rot-Schwarz-Baum, die die Höhe automatisch begrenzen.

Einfügen und Löschen

  • Einfügen: Neue Werte wandern nach der Sortierregel nach unten, bis ein freier Platz gefunden ist — keine Umstrukturierung nötig.
  • Löschen: Ein Blatt wird direkt entfernt, ein Knoten mit einem Kind durch dieses ersetzt; ein Knoten mit zwei Kindern wird durch seinen In-Order-Nachfolger ersetzt.
  • In-Order-Traversierung (links, Knoten, rechts) liefert alle Werte automatisch sortiert — der Baum ist damit selbst eine Sortiermaschine.

Interessante Alternative für schnelle Zugriffe ist die Hash-Tabelle: Sie ist im Mittel schneller (O(1)), kann aber keine sortierte Reihenfolge liefern.

Praxis-Tipps

  • Den Baum balanciert halten (zufällige Einfügereihenfolge hilft oft schon) — sonst drohen O(n)-Entartung.
  • Für Prioritätsaufgaben stattdessen einen Heap verwenden: Er findet Minimum oder Maximum garantiert schnell, unterstützt aber keine allgemeine Suche.
  • Die Grundidee „Eingabe halbieren und links/rechts verzweigen" steckt auch in der binären Suche im Array.

Verwandte Grundlagen: Baum-Datenstruktur, Traversierung, Rekursion, Algorithmus.