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 bei einem balancierten Baum, im entarteten Worst Case in . 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 ), 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:
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).
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.
Anmelden, um den Fortschritt zu speichern.
Nächster Schritt
Aktives Abrufen festigt Wissen schneller als nochmal lesen.
Diese Lerneinheit wurde für typische Bachelor-Klausuren konzipiert. So prüfen wir · Fehler entdeckt? Melde ihn uns oder markiere die fragliche Stelle direkt im Text oben.
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 muss keine Sortier-Invariante haben (z. B. Heap, AST, DOM). Hier behandeln wir den 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:
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: 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.
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 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.
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.
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.
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).
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 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.
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):
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).
| 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) |
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.
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):
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:
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.
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.
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.
Interaktive Visualisierung
Interaktive Komponente: probiere sie im Topic-Player oben aus.
Klausurfragen mit Lösungen (8)
Antwort: Alles links vom Knoten ist kleiner, alles rechts ist größer-gleich (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 erfüllt sie, ebenso der rechte. Konvention in dieser Lerneinheit: links < self, rechts ≥ self (Duplikate gehen rechts). 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: 4 (entartet zur Linked-List)
Erklärung: Bei aufsteigenden Werten wandert jeder neue Knoten ans rechte Ende. Resultat: entartet zur Linked-List mit 5 Knoten, also 4 Kanten. Höhe (Kantenzahl) = 4. Worst-Case-Vergleiche = Höhe+1 = 5. Wird Höhe als Anzahl Ebenen gezählt, wäre die Antwort 5, achte auf die Definition. Suche und Insert sind hier `O(n)`. 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 verarbeiten, dann den Knoten selbst. In **C/C++** vermeidet das Dangling Pointers / Memory Leaks beim manuellen Freigeben. In **Java/Python** übernimmt Garbage Collection die Freigabe, Post-Order bleibt aber logisch sauber, weil Kinder vor dem Parent fertig sind (z. B. zum Auswerten von Ausdrucksbäumen).
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.