Binäre Bäume

Jeder Knoten enthält einen Schlüssel. Für jeden Knoten gilt: Alle Schlüssel im linken Unterbaum < Knotenschlüssel und alle Schlüssel im rechten Unterbaum > Knotenschlüssel. Diese Eigenschaft gilt rekursiv für alle Unterbäume und ermöglicht effiziente Suche durch Halbierung des Suchraums.

Definition: Liefert das kleinste Element ≥ k im Baum. Beispiel bei Baum mit {10, 21, 32, 42, 52, 64, 76}: ceiling(30) → 32 (kleinstes Element ≥ 30), ceiling(42) → 42 (Treffer), ceiling(80) → null (kein größeres Element vorhanden). Ergebnis ist entweder ein Schlüssel oder null.

Fall 1 - Baum ist leer: Gib null zurück.

Fall 2 - Aktueller Schlüssel x == k: x ist perfekter Treffer, gib x zurück (fertig).

Fall 3 - Aktueller Schlüssel x < k: x ist zu klein, nicht als Ergebnis geeignet, suche rekursiv im rechten Unterbaum weiter, gib Ergebnis des rechten Unterbaums zurück.

Fall 4 - Aktueller Schlüssel x > k: x ist Kandidat (≥ k erfüllt), aber im linken Unterbaum könnte ein kleinerer Kandidat existieren, suche rekursiv im linken Unterbaum, falls linker Unterbaum Ergebnis liefert dann ist das besser (nimm das), sonst nimm x als Ergebnis.

Definition: Liefert das größte Element ≤ k im Baum. Beispiel bei Baum mit {10, 21, 32, 42, 52, 64, 76}: floor(45) → 42 (größtes Element ≤ 45), floor(32) → 32 (Treffer), floor(5) → null (kein kleineres Element vorhanden). Konzept: Spiegelbild von ceiling.

Fall 1 - Baum ist leer: Gib null zurück. Fall 2 - Aktueller Schlüssel x == k: x ist perfekter Treffer, gib x zurück. Fall 3 - Aktueller Schlüssel x > k: x ist zu groß, nicht als Ergebnis geeignet, suche rekursiv im linken Unterbaum weiter. Fall 4 - Aktueller Schlüssel x < k: x ist Kandidat (≤ k erfüllt), im rechten Unterbaum könnte ein größerer (aber immer noch ≤ k) Kandidat existieren, suche rekursiv im rechten Unterbaum, falls rechter Unterbaum Ergebnis liefert dann ist das besser, sonst nimm x.

Definition: Liefert das nächstgrößere Element > k (strikt größer). Unterschied zu ceiling: ceiling(k) liefert kleinste Element ≥ k (k selbst möglich), higher(k) liefert kleinste Element > k (k selbst ausgeschlossen). Beispiel bei {10, 21, 32, 42}: ceiling(32) → 32, higher(32) → 42.

Definition: Liefert das nächstkleinere Element < k (strikt kleiner). Unterschied zu floor: floor(k) liefert größte Element ≤ k (k selbst möglich), lower(k) liefert größte Element < k (k selbst ausgeschlossen). Beispiel bei {10, 21, 32, 42}: floor(32) → 32, lower(32) → 21.

Schritt 1 - Suche nach der Einfügeposition: Starte an der Wurzel, in jedem Schritt vergleiche k mit aktuellem Knotenschlüssel.

Schritt 2 - Navigiere durch den Baum: Falls k < aktueller Schlüssel dann gehe nach links, falls k > aktueller Schlüssel dann gehe nach rechts, falls k == aktueller Schlüssel dann existiert Element bereits und kein Einfügen notwendig. Schritt 3 - Erreiche externen Knoten (null): Hier ist die Einfügeposition, erstelle neuen Knoten mit Schlüssel k und füge ihn an dieser Stelle ein. Komplexität: O(h) wobei h = Baumhöhe.

Fall 1 - Knoten hat keine Kinder (Blatt): Einfach entfernen. Fall 2 - Knoten hat genau ein Kind: Knoten durch seinen Unterbaum ersetzen, Beispiel: Lösche 32 dann ersetze durch Unterbaum mit Wurzel 23. Fall 3 - Knoten hat zwei Kinder (schwierigster Fall): Finde Ersatzschlüssel (Minimum des rechten Unterbaums oder Maximum des linken), ersetze Schlüssel des zu löschenden Knotens, lösche den Knoten mit dem Ersatzschlüssel rekursiv.

Gegeben: Knoten n mit Schlüssel k soll gelöscht werden, n hat zwei nicht-leere Unterbäume. Schritt 1 - Finde Ersatzschlüssel: Suche kleinstes Element im rechten Unterbaum (= Minimum rechts), Alternative ist größtes Element im linken Unterbaum. Schritt 2 - Ersetze Schlüssel: Überschreibe k mit dem Ersatzschlüssel. Schritt 3 - Lösche Ersatzknoten: Rufe Löschoperation rekursiv für Ersatzschlüssel im rechten Unterbaum auf, der Ersatzknoten hat maximal ein Kind (rechts) daher einfacher zu löschen. Wichtig: Dies passiert nur einmal, da der Ersatzknoten (Minimum rechts) per Definition keinen linken Unterbaum hat.

Minimum (kleinstes Element): Wiederhole Abstieg nach links bis linker Unterbaum leer ist, der erreichte Knoten enthält das Minimum. Maximum (größtes Element): Wiederhole Abstieg nach rechts bis rechter Unterbaum leer ist, der erreichte Knoten enthält das Maximum. Komplexität: O(h) wobei h = Baumhöhe, Worst Case O(N) bei entartetem Baum, Average Case O(log N).

Fall 1 - Rechter Unterbaum existiert: Nächstgrößerer = Minimum des rechten Unterbaums, Beispiel bei Knoten 42 mit rechtem Unterbaum {64, 52, 76} ist Minimum 52. Fall 2 - Rechter Unterbaum ist leer: Steige im Baum auf, suche ersten rechten Elternknoten (Knoten mit größerem Schlüssel als k), falls bis zur Wurzel keiner gefunden dann existiert kein größerer Schlüssel. Beispiel: Bei Knoten 32 ohne rechten Unterbaum findet Aufstieg 42.

Alle Basisoperationen haben O(h) wobei h = Baumhöhe: Suchen (lookup), Einfügen (insert), Löschen (delete), Minimum/Maximum, ceiling, floor, higher, lower. Worst Case: O(N) bei entartetem Baum (Liste). Average Case: O(log N) bei zufälliger Einfügereihenfolge. Vollständige Traversierung: O(N) da jeder Knoten besucht wird.

Ursache: Sortierte oder fast sortierte Einfügereihenfolge. Beispiel: Einfügen von 10, 21, 32, 42, 52, 64, 76 in dieser Reihenfolge ergibt eine verkettete Liste nach rechts, Baumhöhe = N (statt log N), alle Operationen in O(N) statt O(log N). Lösung: Zufällige Einfügereihenfolge ergibt Average Case O(log N), balancierte Suchbäume (AVL, Red-Black) garantieren O(log N).

In-Order Traversierung (LWR: Links-Wurzel-Rechts): Schritt 1 - Besuche rekursiv den linken Unterbaum, Schritt 2 - Verarbeite die Wurzel (aktuellen Knoten), Schritt 3 - Besuche rekursiv den rechten Unterbaum. Ergebnis: Alle Schlüssel in aufsteigend sortierter Reihenfolge. Beispiel: Baum {42(21(10,32),64(52,76))} ergibt Reihenfolge 10, 21, 32, 42, 52, 64, 76. Komplexität: O(N) da jeder Knoten genau einmal besucht wird.

Sortiertes Array: Suche nach Position O(log N) mit binärer Suche gut, aber Einfügen O(N) wegen Verschieben von N/2 Elementen im Durchschnitt schlecht. BST (Average Case): Suche nach Position O(log N) gut und Einfügen O(log N) nur Zeiger setzen ebenfalls gut. N Einfügungen: Array benötigt O(N²), BST benötigt O(N·log N).

Rekursiv: Vorteile sind eleganter kompakter Code und folgt natürlicher Baumstruktur, Nachteile sind Call-Stack-Overhead und Stack Overflow bei sehr tiefen Bäumen möglich. Iterativ: Vorteile sind kein Rekursionsoverhead und besser bei sehr tiefen Bäumen, Nachteile sind komplexerer Code und benötigt manchmal zusätzliche Datenstrukturen (Stack für Traversierung). Tipp: lookup/insert oft iterativ, delete meist rekursiv.

Gut geeignet: Set, SortedSet, NavigableSet mit O(log N) Operationen, Map, SortedMap, NavigableMap mit O(log N) Operationen, PriorityQueue mit O(log N) für insert/removeMin. Weniger geeignet: FIFO/LIFO Queue da Arrays besser sind (amortisiert O(1)), List mit indiziertem Zugriff da Arrays deutlich besser sind (O(1) vs O(N)). Vorteil von BST: Operationen auf Basis der Schlüsselordnung wie ceiling, floor etc.

Erfolgreiche Suche: Wird vor Erreichen eines externen Knotens (null) abgebrochen sobald der gesuchte Schlüssel gefunden wird. Erfolglose Suche: Endet immer erst in einem externen Knoten (null), muss also immer bis zu einem Blatt traversieren. Konsequenz: Für erfolglose Suchen ist eine durchschnittlich längere Laufzeit zu erwarten da sie einen zusätzlichen Schritt bis zum externen Knoten benötigen.

Höchstens einmal! Der Knoten mit dem kleinsten Schlüssel im rechten Unterbaum (oder größten im linken) ist daran zu erkennen dass sein linker Unterbaum (bzw. rechter) leer ist. Dieser Knoten weist also entweder keinen oder genau einen nicht-leeren Unterbaum auf und kann damit grundsätzlich direkt gelöscht werden (per Entfernen oder per Ersetzen durch den nicht-leeren Unterbaum). Eine weitere Suche nach einem Ersatzschlüssel ist damit nie erforderlich.