Halbierte Suche durch sortierte Baumstruktur: O(log n) für Suche, Insert, Delete — wenn balanciert. Mit BST-Visualizer und allen vier Traversals (In/Pre/Post/Level-Order). Klausur-Liebling.
Ein Binärer Suchbaum ist eine hierarchische Datenstruktur mit der Invariante: linker Teilbaum kleiner, rechter Teilbaum größer als der Wurzelknoten. Dadurch kannst du suchen, einfügen und löschen jeweils in O(log n) bei einem balancierten Baum.
Die zentralen Operationen die du in der Klausur können musst:
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).
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: ca. 1 Vergleich. Aber: keine Reihenfolge, keine Range-Abfragen.
Was wenn du schnell suchen UND schnell einfügen UND sortierte Reihenfolge willst? Da kommt der Binary Search Tree ins Spiel.
Stell dir das Spiel „20 Fragen" vor: ich denke an eine Zahl zwischen 1 und 100, du fragst mich Ja/Nein. Beste Strategie:
Genau das macht ein BST: bei jedem Knoten wird die Suche halbiert.
Jeder Knoten hat höchstens zwei Kinder (links und rechts). Die Regel:
Alles links vom Knoten ist kleiner, alles rechts ist größer.
50 ← Wurzel
/ \
25 75 ← alles links < 50, alles rechts > 50
/ \ / \
10 35 60 90 ← gleiche Regel rekursiv
Beispiel: Suche 35.
Die Invariante ist rekursiv: nicht nur direkte Kinder, sondern der gesamte linke Teilbaum ist kleiner, der gesamte rechte Teilbaum ist größer.
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.
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.
Gibt drei Fälle. Komplexer, aber gleicher Aufwand: O(log n). (Detail folgt in höheren Themen.)
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.
Wenn du alle Knoten in eine Reihenfolge bringen willst, gibt es 4 Standard-Methoden:
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.
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 genügt für eindeutige Rekonstruktion mit In-Order).
Beispiel: 50, 25, 10, 35, 75, 60, 90.
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.
levelorder(root):
queue = [root]
while queue not empty:
node = queue.pop_front()
print(node.value)
queue.append(node.left)
queue.append(node.right)
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).
| Operation | Ausgewogen | Entartet (sortierte Inserts) |
|---|---|---|
| Suchen | O(log n) | O(n) |
| Einfügen | O(log n) | O(n) |
| Löschen | O(log n) | O(n) |
| In-Order alle ausgeben | O(n) | O(n) |
| Min / Max finden | O(log n) | O(n) |
Bei n = 1 Million: O(log n) ≈ 20, O(n) = 1 Million. 50.000-mal schneller, aber nur wenn der Baum balanciert bleibt.
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:
Trick 3 — Anzahl Knoten: ein Baum mit Höhe h hat mindestens h+1 Knoten (entartet) und höchstens 2^(h+1) − 1 (vollständig).
Trick 4 — log₂(n) Heuristik: bei n Knoten ist die minimale Höhe ⌈log₂(n+1)⌉ − 1. Für n=1.000.000 ≈ 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:
Trick 7 — Rekursion: Tree-Operationen sind natürlich rekursiv. Java-Studierende: Stack-Overflow bei tiefen Bäumen (n > 10000) — manche Implementierungen iterativ.
Alle Tabs der Lerneinheit (Erklärung · Interaktiv · Quiz) als durchgehender Text. Ideal zum Wiederholen vor der Klausur — und für Suchmaschinen wie Google, Bing und KI-Suche (ChatGPT, Perplexity).
Ein Binärer Suchbaum ist eine hierarchische Datenstruktur mit der Invariante: linker Teilbaum kleiner, rechter Teilbaum größer als der Wurzelknoten. Dadurch kannst du suchen, einfügen und löschen jeweils in O(log n) bei einem balancierten Baum.
Wie wächst der Aufwand eines Algorithmus mit der Eingabe-Größe? Konstant, linear, quadratisch, und wann macht der Unterschied wirklich was aus?
Der intuitive Sortieralgorithmus: zwei verschachtelte Schleifen, größere Werte blubbern nach oben. Einfach zu erklären, in der Praxis aber zu langsam: O(n²).
Teile und Herrsche. Garantierte O(n log n) durch rekursives Halbieren plus Merge. Stabil, aber braucht O(n) Zusatzspeicher. Klausur-Klassiker schlechthin.
Die zentralen Operationen die du in der Klausur können musst:
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).
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: ca. 1 Vergleich. Aber: keine Reihenfolge, keine Range-Abfragen.
Was wenn du schnell suchen UND schnell einfügen UND sortierte Reihenfolge willst? Da kommt der Binary Search Tree ins Spiel.
Stell dir das Spiel „20 Fragen" vor: ich denke an eine Zahl zwischen 1 und 100, du fragst mich Ja/Nein. Beste Strategie:
Genau das macht ein BST: bei jedem Knoten wird die Suche halbiert.
Jeder Knoten hat höchstens zwei Kinder (links und rechts). Die Regel:
Alles links vom Knoten ist kleiner, alles rechts ist größer.
50 ← Wurzel
/ \
25 75 ← alles links < 50, alles rechts > 50
/ \ / \
10 35 60 90 ← gleiche Regel rekursiv
Beispiel: Suche 35.
Die Invariante ist rekursiv: nicht nur direkte Kinder, sondern der gesamte linke Teilbaum ist kleiner, der gesamte rechte Teilbaum ist größer.
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.
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.
Gibt drei Fälle. Komplexer, aber gleicher Aufwand: O(log n). (Detail folgt in höheren Themen.)
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.
Wenn du alle Knoten in eine Reihenfolge bringen willst, gibt es 4 Standard-Methoden:
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.
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 genügt für eindeutige Rekonstruktion mit In-Order).
Beispiel: 50, 25, 10, 35, 75, 60, 90.
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.
levelorder(root):
queue = [root]
while queue not empty:
node = queue.pop_front()
print(node.value)
queue.append(node.left)
queue.append(node.right)
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).
| Operation | Ausgewogen | Entartet (sortierte Inserts) |
|---|---|---|
| Suchen | O(log n) | O(n) |
| Einfügen | O(log n) | O(n) |
| Löschen | O(log n) | O(n) |
| In-Order alle ausgeben | O(n) | O(n) |
| Min / Max finden | O(log n) | O(n) |
Bei n = 1 Million: O(log n) ≈ 20, O(n) = 1 Million. 50.000-mal schneller, aber nur wenn der Baum balanciert bleibt.
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:
Trick 3 — Anzahl Knoten: ein Baum mit Höhe h hat mindestens h+1 Knoten (entartet) und höchstens 2^(h+1) − 1 (vollständig).
Trick 4 — log₂(n) Heuristik: bei n Knoten ist die minimale Höhe ⌈log₂(n+1)⌉ − 1. Für n=1.000.000 ≈ 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:
Trick 7 — Rekursion: Tree-Operationen sind natürlich rekursiv. Java-Studierende: Stack-Overflow bei tiefen Bäumen (n > 10000) — manche Implementierungen iterativ.
Klick einen Preset oder füge eigene Werte ein. Beobachte:
Probier folgendes:
Interaktive Visualisierung
Binärer Suchbaum mit Insert, Search, Traversal (Inorder, Preorder, Postorder).
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.
Klausurfragen mit Lösungen (8)
Antwort: Alles links vom Knoten ist kleiner, alles rechts ist größer (rekursiv für die ganzen Teilbäume)
Erklärung: BST = Binary Search Tree. Die Sortier-Invariante gilt rekursiv: nicht nur direkte Kinder, sondern der gesamte linke Teilbaum ist kleiner als der Knoten, der gesamte rechte größer. Balancierung ist NICHT garantiert (das macht erst AVL/Red-Black).
Antwort: Etwa 20 (log₂ 1M)
Erklärung: Bei jedem Knoten wird die Suche halbiert. Höhe des balancierten Baums = log₂(n). log₂(1.000.000) ≈ 20. Das ist der Hauptvorteil gegenüber Linked-List (1 Million) und unsortiertem Array.
Antwort: 5 (entartet zur Linked-List)
Erklärung: Bei aufsteigenden Werten wandert jeder neue Knoten ans rechte Ende. Resultat: Linked-List statt Baum, Höhe = Anzahl Knoten = 5. Suche und Insert werden O(n) — derselbe Aufwand wie Linked-List. Genau dafür gibt's selbstbalancierende Bäume.
Antwort: Die Werte aufsteigend sortiert
Erklärung: In-Order = links · self · rechts. Bei BST-Invariante (links < self < rechts) ergibt das automatisch eine sortierte Folge. Klausur-Klassiker: 'gib alle Werte sortiert aus' → In-Order genügt.
Antwort: 50, 25, 10, 35, 75
Erklärung: Pre-Order = self · links · rechts. Erst 50 (Wurzel), dann linker Teilbaum (25 → 10 → 35), dann rechter (75). Antwort A wäre In-Order, C wäre Post-Order, D wäre Level-Order.
Antwort: Level-Order
Erklärung: Level-Order = BFS (Breadth-First Search). Wir besuchen die Knoten Ebene für Ebene mit einer Queue: dequeue, kinder enqueue, repeat. Pre/In/Post sind DFS — Rekursion oder ein Stack.
Antwort: Post-Order
Erklärung: Post-Order = links · rechts · self. Erst Kinder löschen, dann den Knoten selbst. Wenn du Pre-Order machst, würdest du den Parent löschen während die Kinder noch existieren — Speicher-Lecks oder Dangling Pointers.
Antwort: BST: links<self<rechts. Heap: parent ≥ kinder (Max-Heap), aber Geschwister werden nicht verglichen
Erklärung: BST garantiert eine sortierte Reihenfolge (nutzt Inorder), Heap nur dass parent größer/kleiner als seine Kinder ist (für Priority Queue). Heaps sind tatsächlich immer fast vollständig (Höhe ⌈log₂ n⌉), BSTs können entarten.