Binäre Suchbäume

3.1 Definition eines Binären Suchbaums (BST)

Binärer Suchbaum (BST) — ist ein binärer Baum, der die folgenden Eigenschaften besitzt:

• Für jeden Knoten enthält sein linker Teilbaum nur Knoten mit Schlüsseln, die kleiner sind als der Schlüssel des gegebenen Knotens.
• Für jeden Knoten enthält sein rechter Teilbaum nur Knoten mit Schlüsseln, die größer sind als der Schlüssel des gegebenen Knotens.
• Beide Teilbäume jedes Knotens sind ebenfalls binäre Suchbäume.

Beispiel eines BST:

BST – steht für Binary Search Tree – wörtlich „Binärer Suchbaum“. Im Grunde ist es eine Datenorganisation in Form eines „Baums“, in dem sehr schnell gesucht werden kann. Die Baumstruktur ist im Wesentlichen eine versteckte/geschickte Sortierung von Elementen.

In-order Traversal

Traversal-Aufgabe — besteht darin, eine Liste der Knoten auf eine bestimmte Weise zu erstellen (oder Daten aus den Knoten, eine Terminologiefrage, die in der Praxis relevant ist). In-order Traversal – ist ein Traversal, bei dem der Baumstamm zwischen den Ergebnissen der entsprechenden Traversals des linken und rechten Teilbaums steht.

Zusammen mit der Eigenschaft des Binären Suchbaums (die von Ungleichheiten spricht, siehe Theorie) bedeutet das, dass ein In-order Traversal des Binären Suchbaums eine sortierte Liste von Knoten ergibt – cool! So sieht das Traversal des zuvor definierten Baumes aus:

3.2 Funktionsprinzipien und Eigenschaften von BST

Funktionsprinzipien:

• Datenorganisation: BST organisiert Daten so, dass ein effizienter Zugriff, Einfügen und Löschen von Elementen gewährleistet wird.
• Rekursive Struktur: Jeder Knoten in BST unterliegt denselben Regeln wie der Baumstamm, was die Struktur rekursiv macht.
• Balancierung: Um optimale Leistung zu gewährleisten, sollte ein BST ausgeglichen sein, das heißt, die Höhe des linken und rechten Teilbaums sollte ungefähr gleich sein.

Eigenschaften von BST:

• Ordnung: Man kann den Baum jederzeit in "In-order"-Reihenfolge durchlaufen (linker Teilbaum → aktueller Knoten → rechter Teilbaum), um alle Elemente in sortierter Reihenfolge zu erhalten.
• Zeit für Operationen:
  • Im Durchschnitt beträgt die Zeit für Such-, Einfüge- und Löschoperationen O(log n), wobei n die Anzahl der Knoten ist.
  • Im schlimmsten Fall (wenn der Baum nicht ausgeglichen ist) kann die Ausführungszeit der Operationen bis zu O(n) betragen.
• Einzigartige Schlüssel: Alle Schlüssel in einem BST müssen einzigartig sein, um die Ordnung zu bewahren.

3.3 Grundlegende Operationen

1. Einfügen (Insertion):

Funktionsprinzip:

• Starte mit dem Wurzelknoten.
• Vergleiche den Schlüssel des neuen Knotens mit dem Schlüssel des aktuellen Knotens.
• Ist der neue Schlüssel kleiner, gehe zum linken Teilbaum, ist er größer — zum rechten.
• Wiederhole den Prozess, bis ein geeigneter Platz zum Einfügen des neuen Knotens gefunden ist (entweder linker oder rechter Nachfolger fehlt).

Algorithmus:

1. Falls der Baum leer ist, wird der neue Knoten zum Wurzelknoten.
2. Ansonsten finde rekursiv den richtigen Platz und füge den neuen Knoten hinzu.

2. Löschen (Deletion):

Funktionsprinzip:

• Finde den Knoten zum Löschen.
• Betrachte drei Fälle:
• Der Knoten ist ein Blatt (hat keine Kinder): Einfach löschen.
• Der Knoten hat ein Kind: Ersetze den Knoten durch sein Kind.
• Der Knoten hat zwei Kinder: Finde den kleinsten Knoten im rechten Teilbaum (oder größten im linken), kopiere seinen Wert in den zu löschenden Knoten und lösche rekursiv den kleinsten Knoten im rechten Teilbaum.

Algorithmus:

1. Finde den Knoten mit dem gegebenen Schlüssel.
2. Je nach Situation führe die passende Lösch- und Umverteilungsoperation aus.

3. Suche (Search):

Funktionsprinzip:

• Starte mit dem Wurzelknoten.
• Vergleiche den Schlüssel des gesuchten Knotens mit dem Schlüssel des aktuellen Knotens.
• Wenn der Schlüssel übereinstimmt, gib den Knoten zurück.
• Ist der Schlüssel kleiner, gehe zum linken Teilbaum, ist er größer — zum rechten.
• Wiederhole den Prozess, bis der Knoten mit dem gesuchten Schlüssel gefunden ist oder das Ende des Baumes erreicht ist (in diesem Fall ist der Knoten nicht gefunden).

Algorithmus:

1. Falls der Baum leer ist oder der Schlüssel des Knotens mit dem gesuchten übereinstimmt, gib den Knoten zurück.
2. Ist der Schlüssel des gesuchten Knotens kleiner, suche rekursiv im linken Teilbaum.
3. Ist der Schlüssel des gesuchten Knotens größer, suche rekursiv im rechten Teilbaum.

3.4 Beispielaufgaben, die mit BST gelöst werden können

1. Suche eines Elements in einer dynamischen Menge

Es ist nötig, eine Menge von Zahlen zu pflegen, in die neue Elemente hinzugefügt, bestehende gelöscht und schnell überprüft werden können, ob eine gegebene Zahl in der Menge ist.

Lösung mit BST:

• Einfügen neuer Elemente in den Baum.
• Löschen bestehender Elemente.
• Suche von Elementen im Baum.

Anwendungsbeispiel:

Verwaltung einer Liste registrierter Benutzer in einem System, bei dem Benutzer hinzugefügt und entfernt werden können, und das System muss schnell überprüfen, ob ein Benutzer registriert ist.

2. Auffinden des minimalen und maximalen Elements

Es ist nötig, schnell die minimalen und maximalen Werte in einem Datensatz zu finden.

Lösung mit BST:

• Das minimale Element befindet sich im äußersten linken Knoten des Baumes.
• Das maximale Element befindet sich im äußersten rechten Knoten des Baumes.

Anwendungsbeispiel:

Verwaltung eines Systems, das Aktienkurse verfolgt, bei dem es erforderlich ist, schnell den minimalen und maximalen Preis zu einem bestimmten Zeitpunkt zu finden.

3. Überprüfung der Ausgewogenheit eines Ausdrucks

Ein mathematischer Ausdruck ist gegeben, es ist nötig, seine Ausgewogenheit hinsichtlich der Anzahl der offenen und schließenden Klammern zu überprüfen.

Lösung mit BST:

Verwende einen BST, um Zwischenzustände zur Überprüfung der Ausgewogenheit von Klammern zu speichern.

Anwendungsbeispiel:

Parsen und Kompilieren von Code, bei dem die korrekte Platzierung von Klammern in Ausdrücken überprüft werden muss.

4. Aufbau eines Wörterbuchs

Es ist nötig, eine Datenstruktur für die Speicherung eines Wörterbuchs zu erstellen, in dem Wörter hinzugefügt, gelöscht und schnell gefunden werden können.

Lösung mit BST:

• Wörter werden in alphabetischer Reihenfolge in den Baum eingefügt.
• Die Suche nach Wörtern erfolgt anhand ihrer Schlüssel.

Anwendungsbeispiel:

Ein Autokorrektursystem, bei dem Wörter schnell gefunden und korrigiert werden müssen.