Binärer Suchbaum

aus Wikipedia, der freien Enzyklopädie

Ein binärer Suchbaum mit der Größe 9, der Tiefe 3, Wurzel 8 und den Blättern 1, 4, 7 und 13.

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 oder gleichgroße 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.

Inhaltsverzeichnis

1 Suchen in binären Suchbäumen
- 1.1 Komplexität
2 Einfügen in binären Suchbäumen
3 Löschen in binären Suchbäumen
4 Pseudocode
5 Rotation in binären Suchbäumen
- 5.1 Komplexität
6 Siehe auch

[Bearbeiten] 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[x]
 2      dann ergebnis: x
 3  wenn s < schlüssel[x]
 4      dann ergebnis: suche(wurzel_linker_teilbaum[x], s)
 5      sonst ergebnis: suche(wurzel_rechter_teilbaum[x], s)

[Bearbeiten] 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 bei häufigem Löschen verschlechtert.

Siehe auch: O-Notation

[Bearbeiten] 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

Durch wiederholtes Einfügen von aufsteigend oder absteigend sortierten Werten kann es dazu kommen, dass der Baum nicht mehr balanciert ist, sondern zu einer linearen Liste entartet.

[Bearbeiten] 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

Üblich ist es jedoch, den zu löschenden Knoten durch den symmetrischen Vorgänger oder Nachfolger zu ersetzen. Der symmetrische Vorgänger (im Beispiel F) ist der größte Wert im linken Teilbaum, steht also dort ganz rechts. Dementsprechend ist der symmetrische Nachfolger (im Beispiel J) der kleinste Wert im rechten Teilbaum und steht dort ganz links. Der symmetrische Vorgänger (Nachfolger) kann einen linken (rechten) Teilbaum haben, der an die Stelle gehängt werden muss, wo der symmetrische Vorgänger (Nachfolger) war. Die Höhe des Baumes wird dadurch nicht größer und der Baum damit nicht so stark entartet.

Im folgenden Beispiel wird der zu löschende Knoten G durch den symmetrischen Nachfolger J ersetzt:

            S                  S
          /   \              /   \
         G     W            J     W
       /  \               /  \
      D     M            D     M
     / \   / \          / \   / \
    B   F J   P        B   F K   P
           \
            K

Durch wiederholtes Löschen kann es dazu kommen, 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.

[Bearbeiten] Pseudocode

Um das Löschen eines Elements, das zwei Nachfolger besitzt, aus einem binären Suchbaum besser zu verstehen, soll der Pseudocode helfen.

Ein binärer Suchbaum der Knoten 5 gelöscht werden soll

Löschen( T, x )

   knoten y 
   knoten z
 1  if x.left = NULL || x.right = NULL
 2     then y = z 
 3     else y = baumNextSuche ( T, x )

 4  if y.left!=NULL
 5     then z = y.left
 6     else z = y.right

 7  if z!=NULL                 
 8     then z.parent = y.parent

Der neue Baum

 9  if y.parent = NULL                                      
10     then T.root = z                     
11     else if y = y.parent.left              
12                    then y.parent.left = z        
13                    else y.parent.right = z
   
14  if y!=x
15     then x.key = y.key;

[Bearbeiten] 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.