Binärer Suchbaum (BST)

Hinweis: Ein allgemeiner Binärbaum muss keine Sortier-Invariante haben (z. B. Heap, AST, DOM). Hier behandeln wir den Binary Search Tree (BST) als Spezialfall, den klausur-relevanten Fall.

Ein Binärer Suchbaum ist eine hierarchische Datenstruktur mit der Invariante: linker Teilbaum kleiner als der Knoten, rechter Teilbaum größer (oder gleich, je nach Konvention, wir nehmen >= rechts; andere Kurse verbieten Duplikate oder zählen sie im Knoten). Dadurch kannst du suchen, einfügen und löschen jeweils in O(log n) bei einem balancierten Baum, im entarteten Worst Case in O(n). Du lernst hier die Standard-Operationen (search/insert/delete), die drei Lösch-Fälle (Blatt, ein Kind, zwei Kinder mit In-Order-Successor-Ersatz), die vier wichtigsten Traversierungen (In-Order liefert sortierte Folge, Pre-Order/Post-Order für Baum-Rekonstruktion, Level-Order via BFS), warum ein normaler BST sich nicht selbst balanciert (deswegen AVL- oder Red-Black-Trees für garantiertes O(log n)), die Höhen-Konvention (Anzahl Kanten vs Anzahl Knoten , wir nehmen Kanten, Wurzel hat Höhe 0) und die Rekonstruktions-Eindeutigkeit: Pre-Order + In-Order (oder Post-Order + In-Order) erlauben eindeutige Rekonstruktion bei eindeutigen Werten.

Die zentralen Operationen die du in der Klausur können musst:

• Suchen: starte an der Wurzel, gehe links wenn gesucht < aktuell, rechts wenn gesucht > aktuell
• Einfügen: wie Suchen, am Ende neuen Knoten als Blatt anhängen
• Löschen: drei Fälle (kein Kind, ein Kind, zwei Kinder mit In-Order-Successor)
• Traversierung: In-Order liefert die Werte sortiert, Pre-/Post-Order für andere Anwendungsfälle

In Klausuren wird oft gefragt: gegeben eine Einfüge-Reihenfolge, zeichne den Baum und gib die In-Order-Traversierung an. Vorsicht bei sortierten Eingaben: der Baum entartet zu einer Liste, dann ist alles O(n).

Das Problem

Du hast eine Telefonnummer-Sammlung mit 1 Million Einträgen. Frage: "Hat Anna eine Nummer hier drin?"

Linked-List: einer nach dem anderen prüfen → bis zu 1 Million Vergleiche.

Sortiertes Array: binäre Suche → ca. 20 Vergleiche. Aber: einfügen ist langsam (alles verschieben).

Hashtabelle: durchschnittlich sehr schnelle exakte Lookups, typischerweise O(1). Aber: keine effiziente sortierte Traversierung, keine Range-Abfragen wie bei Suchbäumen.

Was wenn du schnell suchen UND schnell einfügen UND sortierte Reihenfolge willst? Da kommt der Binary Search Tree ins Spiel.

Die Idee

Stell dir das Spiel „20 Fragen" vor: ich denke an eine Zahl zwischen 1 und 100, du fragst mich Ja/Nein. Beste Strategie:

• „Größer oder kleiner als 50?" → Hälfte weg
• „Größer oder kleiner als 25?" (wenn unter 50) → noch mal Hälfte weg
• ... in log₂(100) ≈ 7 Fragen bist du fertig.

Genau das macht ein balancierter BST: bei jedem Vergleich wird ein Teilbaum ausgeschlossen, in der Größe ungefähr halbiert. Bei einem entarteten BST kann die Suche linear werden, siehe weiter unten.

Die BST-Invariante

Jeder Knoten hat höchstens zwei Kinder (links und rechts). Die Regel in dieser Lerneinheit (kompatibel mit unserem Insert-Code):

Linker Teilbaum: alle Werte < Knotenwert. Rechter Teilbaum: alle Werte ≥ Knotenwert.

Damit landen Duplikate per Konvention im rechten Teilbaum. In-Order-Traversal liefert dann eine nicht-fallende (statt streng aufsteigende) Folge. Andere Bücher verbieten Duplikate im BST komplett oder zählen sie pro Knoten mit, beide Konventionen sind gültig.

Duplikate im BST (Mini-Box):

• Diese Lerneinheit: < links, ≥ rechts → Duplikate landen rechts.
• Alternative 1: ≤ links, > rechts → Duplikate landen links.
• Alternative 2: Duplikate komplett verbieten (Set-Semantik) → Insert eines existierenden Werts ist ein No-Op oder Fehler.
• Alternative 3: Count pro Knoten → kein neuer Knoten, sondern count++ am bestehenden.

Klausur-Falle: bei Duplikaten ist die Rekonstruktion aus Pre-Order + In-Order nicht mehr eindeutig, weil In-Order mehrere identische Werte hintereinander liefert ohne Positions-Information.

              50              ← Wurzel
            /    \
          25       75         ← alles links < 50, alles rechts > 50
         /  \    /  \
       10   35  60   90       ← gleiche Regel rekursiv

Beispiel: Suche 35.

• Bei 50: 35 < 50 → links
• Bei 25: 35 > 25 → rechts
• Bei 35: gefunden! 3 Vergleiche statt 7.

Die Invariante ist rekursiv: nicht nur direkte Kinder, sondern der gesamte linke Teilbaum ist kleiner, der gesamte rechte Teilbaum ist größer.

Operationen

Suchen (search)

function search(node, target):
    if node == null:
        return "nicht gefunden"
    if target == node.value:
        return "gefunden!"
    if target < node.value:
        return search(node.left, target)    // nach links
    else:
        return search(node.right, target)   // nach rechts

Bei jedem Schritt halbiert sich der Suchbereich. Höhe des Baumes = ca. log₂(n) → O(log n) im Idealfall.

Einfügen (insert)

Genau wie Suchen, aber wenn du am Ende ankommst (null), hängst du den neuen Knoten dort an.

function insert(node, value):
    if node == null:
        return new Node(value)            // hier eingefügt
    if value < node.value:
        node.left = insert(node.left, value)
    else:
        node.right = insert(node.right, value)
    return node

Beispiel: in den Baum oben 42 einfügen.

• Bei 50: 42 < 50 → links
• Bei 25: 42 > 25 → rechts
• Bei 35: 42 > 35 → rechts
• Bei null: hier ankommen → neuen Knoten 42 anhängen

Löschen (delete) im Detail

Löschen ist der trickreichste Fall und in jeder BST-Klausur ein Klassiker. Aufwand: O(h) mit h = Baumhöhe. Bei balanciertem Baum O(log n), bei entartetem Baum O(n). Es gibt drei Fälle:

Fall 1: Knoten ist Blatt (kein Kind). Einfach abhängen, Parent-Pointer auf null setzen.

   50              50
  /  \    →      /  \
 25  75         25  75
 /              /
10             (10 entfernt)

Fall 2: Knoten hat genau ein Kind. Das Kind rückt an die Stelle des gelöschten Knotens.

   50              50
  /  \    →      /  \
 25  75         25  75
   \               \
   35             (25 entfernt, 35 rückt hoch)
                  →  35 sitzt jetzt wo 25 war

Fall 3: Knoten hat zwei Kinder. Schwierigster Fall. Standardlösung: In-Order-Successor finden (der kleinste Knoten im rechten Teilbaum), seinen Wert in den zu löschenden Knoten kopieren, dann den Successor rekursiv löschen (der hat per Definition höchstens ein rechtes Kind, also Fall 1 oder 2).

   50              60
  /  \    →      /  \
 25  75         25  75    ← 60 ist der In-Order-Successor von 50
    /  \           \         (kleinster Wert im rechten Teilbaum von 50)
   60  90          90

Pseudocode für alle drei Fälle:

function delete(node, value):
    if node == null:
        return null
    if value < node.value:
        node.left = delete(node.left, value)
    elif value > node.value:
        node.right = delete(node.right, value)
    else:
        # Knoten gefunden, drei Fälle
        if node.left == null and node.right == null:
            return null                              # Fall 1: Blatt
        if node.left == null:
            return node.right                       # Fall 2a: nur rechtes Kind
        if node.right == null:
            return node.left                        # Fall 2b: nur linkes Kind
        # Fall 3: zwei Kinder
        successor = findMin(node.right)             # kleinster im rechten Teilbaum
        node.value = successor.value
        node.right = delete(node.right, successor.value)
    return node

function findMin(node):
    while node.left != null:
        node = node.left
    return node

Symmetrisch könnte man auch den In-Order-Vorgänger (größter Wert im linken Teilbaum) nehmen, beide Varianten sind korrekt. Achtung Klausur: bei Duplikaten im BST muss die Lösch-Logik konsistent zur Insert-Konvention sein (wir nehmen ≥ rechts, also stehen Duplikate rechts und Fall 3 trifft sie).

Reihenfolge der Inserts ist KRITISCH

Selbe Werte, andere Reihenfolge → komplett anderer Baum.

Inserts: 50, 25, 75, 10, 35, 60, 90    ← mittig zuerst
                50
              /    \
            25      75
           / \    / \
         10  35  60  90                ← schön ausgewogen, Höhe 3

Inserts: 10, 25, 50, 60, 75, 90        ← aufsteigend
        10
          \
           25
             \
              50
                \
                 60
                   \
                    75
                      \
                       90              ← entartet zur Linked-List, Höhe 6

Aufsteigende Inserts → Linked-List → O(n) statt O(log n). Genau hier liegt das Problem mit naivem BST.

In der Praxis nutzt man selbstbalancierende Bäume (AVL, Red-Black), die garantieren Höhe O(log n) automatisch. TreeMap und TreeSet in Java sind Red-Black-Trees.

Traversal: einen Baum durchlaufen

Wenn du alle Knoten in eine Reihenfolge bringen willst, gibt es 4 Standard-Methoden:

In-Order: links → self → rechts

inorder(node):
    inorder(node.left)
    print(node.value)
    inorder(node.right)

Bei einem BST ist In-Order IMMER sortiert aufsteigend. Wenn du sagen sollst „gib alle Werte sortiert aus", In-Order.

Beispiel auf dem Baum oben: 10, 25, 35, 50, 60, 75, 90.

Pre-Order: self → links → rechts

preorder(node):
    print(node.value)
    preorder(node.left)
    preorder(node.right)

Wurzel zuerst, dann der ganze linke Teilbaum, dann rechts. Anwendung: Klonen eines Baums oder Speichern. Pre-Order allein reicht nicht für eindeutige Rekonstruktion, aber Pre-Order + In-Order rekonstruiert einen Binärbaum eindeutig, sofern die Werte eindeutig sind.

Beispiel: 50, 25, 10, 35, 75, 60, 90.

Post-Order: links → rechts → self

postorder(node):
    postorder(node.left)
    postorder(node.right)
    print(node.value)

Blätter zuerst, Wurzel zuletzt. Anwendung: Speicher freigeben (Kinder vor dem Parent löschen), Berechnung mit abhängigen Werten (Auswerten von Ausdrucksbäumen).

Beispiel: 10, 35, 25, 60, 90, 75, 50.

Level-Order: Ebene für Ebene (BFS)

levelorder(root):
    if root == null: return
    queue = [root]
    while queue not empty:
        node = queue.pop_front()
        print(node.value)
        if node.left != null:  queue.append(node.left)
        if node.right != null: queue.append(node.right)

Wichtig: vor dem Enqueue auf null prüfen, sonst landet null in der Queue und beim nächsten node.value knallt es. Wie ein Wasserfall: Wurzel zuerst, dann Ebene 1 von links nach rechts, dann Ebene 2, etc.

Beispiel: 50, 25, 75, 10, 35, 60, 90.

Pre/In/Post sind DFS (Depth-First, mit Rekursion oder Stack). Level-Order ist BFS (Breadth-First, mit Queue).

Big-O auf einen Blick

Allgemein gilt für Such-/Insert-/Delete-Operationen: normaler BST O(h), balanciert ist h ≈ log n, entartet h ≈ n. AVL- und Red-Black-Trees garantieren h = O(log n) durch automatisches Rebalancing nach jeder Modifikation, dadurch immer O(log n) unabhängig von der Insert-Reihenfolge.

Bei n = 1 Million: O(log n) ≈ 20, O(n) = 1 Million. 50.000-mal schneller, aber nur wenn der Baum balanciert bleibt.

Klausur-Tricks

Trick 1, In-Order erkennen: wenn die Aufgabe „sortiere die Werte" oder „gib aufsteigend aus" ist → In-Order, fertig.

Trick 2, Höhe vs. Tiefe (Konvention in dieser Lerneinheit: Höhe = Anzahl Kanten):

• Tiefe eines Knotens = Anzahl Kanten von der Wurzel bis dorthin (Wurzel hat Tiefe 0)
• Höhe eines Knotens = Anzahl Kanten zum tiefsten Nachfolger-Blatt (Blatt hat Höhe 0)
• Höhe der Wurzel = Höhe des gesamten Baums
• Worst-Case-Vergleiche bei Suche = h+1 (Anzahl Knoten auf dem Pfad)

Manche Bücher zählen Höhe als Anzahl Ebenen (Wurzel hat Höhe 1). Dann sind Worst-Case-Vergleiche genau die Höhe. Achte in Klausuren auf die Definition.

Trick 3, Anzahl Knoten (Kantenhöhe): ein Baum mit Höhe h hat mindestens h+1 Knoten (entartet zur Liste) und höchstens 2^(h+1) - 1 (vollständig).

Trick 4, log₂(n) Heuristik: bei n Knoten ist die minimale Höhe lceil log₂(n+1) rceil - 1 (Kantenhöhe). Für n = 10⁶ ≈ 20.

Trick 5, Insert-Reihenfolge erkennen: wenn Klausur fragt „kann diese Insert-Reihenfolge zu DIESEM Baum führen?", Wurzel kommt als erste rein. Innere Knoten vor ihren Kindern.

Trick 6, BST vs. Heap: beide sind Bäume, aber:

• BST: links < self ≤ rechts (rekursiv für die ganzen Teilbäume)
• Heap: parent ≥ kinder (Max-Heap) oder ≤ (Min-Heap), aber kein Vergleich zwischen Geschwistern
• Heap → Priority Queue, BST → sortierte Map

Trick 7, Rekursion: Tree-Operationen sind natürlich rekursiv. Bei sehr tiefen/entarteten Bäumen kann rekursive Implementierung zum Stack Overflow führen. Die konkrete Grenze hängt von Laufzeitumgebung und Stackgröße ab, manche Implementierungen daher iterativ.

Trick 8, Eindeutige Rekonstruktion: Pre-Order allein reicht nicht eindeutig. Pre-Order + In-Order rekonstruiert einen Binärbaum eindeutig, sofern die Werte eindeutig sind. Analog Post-Order + In-Order. Bei Duplikaten ist die Rekonstruktion aus Pre-Order + In-Order nicht mehr eindeutig, weil In-Order mehrere identische Werte hintereinander liefert ohne Position im Baum.

Trick 9, Höhenkonvention prüfen: in jeder Klausur erst checken, ob Höhe als Anzahl Kanten (Wurzel-Höhe 0) oder Anzahl Ebenen (Wurzel-Höhe 1) gezählt wird. Die Formel für Worst-Case-Vergleiche verschiebt sich um 1.

Trick 10, Balance-Anforderung lesen: bei sortierten Eingaben entartet ein naiver BST. Frag dich immer ob die Aufgabe explizit AVL/Red-Black verlangt oder ob ein normaler BST gemeint ist.

Wo brauchst du Trees?

• java.util.TreeMap, TreeSet: Red-Black-Tree intern, O(log n) Operationen
• Filesystem: Verzeichnisstruktur ist ein Baum
• HTML/XML/JSON: jeder Parser baut einen Syntax-Tree
• Compiler / Interpreter: AST (Abstract Syntax Tree)
• Datenbanken: B-Trees / B+Trees als Index-Struktur
• Spiele: Decision Trees, Behavior Trees, Monte-Carlo-Trees in der KI
• ML: Decision Trees, Random Forests

BST-Spielwiese

Klick einen Preset oder füge eigene Werte ein. Beobachte:

• Suchen zeigt den Pfad in Vermillion, bei jedem Knoten wird halbiert.
• In-Order auf einem BST liefert IMMER eine sortierte Reihenfolge.
• Sortiert (entartet) zeigt warum naive BSTs in der Klausur als Negativbeispiel kommen, wird zur Linked-List.
• Höhe im Header (= Anzahl Kanten zum tiefsten Blatt). Worst-Case-Vergleiche bei Suche = Höhe + 1, also Anzahl Knoten auf dem Pfad.

Probier folgendes:

• Lade Ausgewogen, suche 35 → Pfad 50 → 25 → 35 (3 Vergleiche, Höhe 2)
• Lade Sortiert (entartet) (5 aufsteigend eingefügte Werte), suche das letzte Element → 5 Vergleiche, Höhe 4 (Kantenhöhe)
• Lade Klein, klick In-Order → 1, 3, 6, 8, 10, 12, 14 (sortiert)
• Klick Pre-Order → 8, 3, 1, 6, 12, 10, 14 (Wurzel immer zuerst)

Faustregel zum Mitnehmen: BST = halbierte Suche, aber nur wenn balanciert. Aufsteigende Inserts → entartet → O(n). In der Praxis: Red-Black-Tree (TreeMap, TreeSet in Java) übernimmt das Balancing automatisch.

---

Code-Stepper: BST In-Order-Traversal mit Call-Stack

In-Order auf einem BST liefert immer eine sortierte Reihenfolge. Hier siehst du warum: die rekursive Reihenfolge ist erst links absteigen, dann root drucken, dann rechts. Wir steppen den ausgewogenen Beispiel-Baum mit Wurzel 8 durch und du beobachtest den Call-Stack wachsen und Werte in der Konsole sortiert erscheinen.