Binärer Suchbaum

In der Informatik ist ein binärer Suchbaum eine spezielle Implementierung der abstrakten Datenstruktur Suchbaum. Ein binärer Suchbaum ist ein binärer Baum, bei dem die Knoten des linken Teilbaums eines Knotens nur kleinere Werte und die Knoten des rechten Teilbaums eines Knotens nur größere Werte als der Knoten selbst besitzen.

Binäre Suchbäume sind in der Regel effizienter als lineare Datenstrukturen wie verkettete Listen, da man in ihnen schneller suchen und Elemente einfügen kann. Jedoch können sie zu einer verketteten Liste entarten; deshalb wurden verbesserte Varianten wie z.B. AVL-Bäume entwickelt.

Führt man bei einem binären Suchbaum einen InOrder-Durchlauf aus, so erhält man eine sortierte Liste der Einträge.

Suchen in binären Suchbäumen

Die Suche nach einem Eintrag verläuft derart, dass zunächst der Wert der Wurzel mit dem Suchschlüssel verglichen wird. Sind beide gleich, so ist der Eintrag gefunden.

Andernfalls wird überprüft, ob der Suchschlüssel kleiner ist als der Knotenwert: dann wird die Suche rekursiv im linken Teilbaum der Wurzel fortgeführt; gibt es keinen linken Teilbaum, so existiert der gesuchte Eintrag im binären Baum nicht.

Ist der Suchschlüssel größer, so wird entsprechend im rechten Teilbaum weitergesucht.

Der folgende Pseudocode illustriert die Arbeitsweise des Algorithmus: x: Wurzel des Suchbaums s: gesuchter Schlüssel suche(x, s) 1 wenn x = null oder s = schlüssel^* 2 dann ergebnis: x 3 wenn s < schlüssel^* 4 dann ergebnis: suche(wurzel_linker_teilbaum^*, s) 5 sonst ergebnis: suche(wurzel_rechter_teilbaum^*, s)

Komplexität

Da die Suchoperation entlang eines Weges von der Wurzel zu einem Blatt verläuft, hängt die aufgewendete Zeit im schlechtesten Fall linear von der Tiefe h des Suchbaums ab (Komplexität O(h)).

Die Höhe h ist für den Worst Case immer genauso groß wie die Anzahl der vorhanden Elemente n, damit muss jedes einzufügende Element n, n-1 Elemente durchlaufen. Dies jedoch für alle einzufügenden Elemente. Damit erhält man die Aufsummierung aller Zahlen kleiner n:

$O\left(((n-1)+1) \cdot {{n-1}\over 2}\right) = O(n^2-n) \cdot o(0{,}5) = O(n^2-n)$

Der Best Case ist jedoch schon wesentlich schöner. Geht man von $2^d=c+1$ mit d als Tiefe/Höhe und c als Anzahl der im Baum enthaltenen Elemente aus, so erhält man folgende Komplexitätsrechnung.

$2^d=c+1 \Leftrightarrow d=\log_2 (c+1) \approx \log_2 c$

$O(\lim_{a \to 0} \int_{a}^{n} {\log_2 c\, \mathrm{d}c}) = O(\lim_{a \to 0} \int_{a}^{n} {\ln c\, \mathrm{d}c}) \cdot o\left({1 \over \ln 2}\right) = \mathbf{O(n \cdot \ln n - n)}$

Vollständig gefüllte binäre Suchbäume sowie balancierte Suchbäume haben eine Höhe von O(log n) und ermöglichen so die Suche in logarithmischer Laufzeit. Dies gilt sogar im Durchschnitt für zufällig erzeugte Suchbäume, wenn die folgenden Bedingungen erfüllt sind:

Die Erzeugung des Baumes geschieht nur durch Einfügungen (d.h. ohne Anwendung der 'asymmetrischen' Löschoperation).
Alle Permutationen der zu speichernden Elemente sind gleich wahrscheinlich.

Durch häufige Anwendung der Löschoperation wird ein binärer Suchbaum jedoch linkslastig, so dass sich das Laufzeitverhalten beim häufigem Löschen verschlechtert.

Siehe auch: O-Notation

Einfügen in binären Suchbäumen

Das Einfügen funktioniert nach dem gleichen Prinzip wie das Suchen. Dabei endet die Suche nach dem einzufügenden Element an einem Knoten u.U. erfolglos. Man lässt nun einfach diesen Knoten auf das neue Element verweisen, damit ist dieses korrekt eingefügt. Die Komplexität der Einfügeoperation entspricht somit der Komplexität der Suchoperation.

Nach dem Einfügen ist das neue Element ein Blatt des Suchbaums.

Im folgenden Beispiel wird ein Knoten mit dem Wert 'J' in einen binären Suchbaum eingefügt.

S S / \ / \ / \ / \ G W G W / \ / \ / \ => / \ D M D M / \ \ / \ / \ / \ \ / \ / \ B F P B F J P

Löschen in binären Suchbäumen

Das Löschen ist trivial, wenn der zu löschende Knoten ein Blatt ist: dann wird er einfach entfernt.

Auch wenn der zu löschende Knoten nur einen Nachfolger hat, ist das Löschen recht einfach: der Nachfolger wird an die Stelle gesetzt, an der der zu löschende Knoten war.

Hat der zu löschende Knoten zwei Nachfolger, so ist die eine Möglichkeit, den linken Teilbaum an die Position zu setzen, an der der zu löschende Knoten war, und den rechten Teilbaum rechts an den linken anzuhängen, wie es das Beispiel zeigt:

S S / \ / \ / \ / \ G W D W / \ / \ / \ => / \ D M B F / \ / \ \ / \ / \ \ B F J P M / \ / \ J P

Eine andere Möglichkeit wäre, im rechten Teilbaum nach dem kleinsten Wert zu suchen. Dies ist bei einem Binären Suchbaum der Knoten der im Teilbaum am weitesten links steht. Dieser ersetzt dann den zu löschenden Knoten. Der Knoten J würde also den Knoten G ersetzen.

Durch wiederholtes Löschen kommt es dazu, dass der Baum nicht mehr balanciert ist, sondern zu einer linearen Liste entartet.

Die Komplexität der Löschoperation ist ebenfalls O(h), wobei h die Höhe des Baumes ist.

Eine andere Möglichkeit, bei der der Baum nicht so stark entartet, ist, den InOrder-Nachfolger an die Stelle des gelöschten Elements zu setzen.

Alternativ kann man auch den größten Wert im linken Teilbaum (relativ zu dem zu löschenden Element) oder den kleinsten Wert im rechten Teilbaum an die Stelle des zu löschenden Elements setzen.

Rotation in binären Suchbäumen

Rotationen werden benötigt, um die Bedingungen von balancierten Bäumen (bspw. Rot-Schwarz-Bäumen) wieder herzustellen.

W S / \ Right-Rotate(T,W) / \ / \

> / \ S Y G W / \ <

/ \ / \ Left-Rotate(T,S) / \ G U U Y

Erklärung zu Right-Rotate(T,W):

W mit rechtem Teilbaum wird zum rechten Teilbaum von S. Der ursprüngliche rechte Teilbaum U von S wird zum linken Teilbaum von W. Der rechte Teilbaum Y von W bleibt an seiner Position.

Erklärung zu Left-Rotate(T,S):

S mit linkem Teilbaum wird zum linken Teilbaum von W. Der ursprüngliche linke Teilbaum U von W wird zum rechten Teilbaum von S. Der rechte Teilbaum Y von W bleibt an seiner Position.

Rotationen verletzen die Suchbaum-Eigenschaften nicht, also ist nach ihrer Anwendung ein korrekter Suchbaum vorhanden.

Komplexität

Rotationen benötigen konstante Laufzeit O(1).

Siehe auch

Baum, B-Baum, Entscheidungsbaum, Binärbaum, Balancierter Baum, Rot-Schwarz-Baum.

Suchbaum

Gourt Home::Gourt :: Binärer Suchbaum

Suchen in binären Suchbäumen

Komplexität

Einfügen in binären Suchbäumen

Löschen in binären Suchbäumen

Rotation in binären Suchbäumen

Komplexität

Siehe auch