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[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)

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

Höhe

Der Abstand der Wurzel bis zum unteresten Blatt wird als die Baumhöhe bezeichnet. Die optimale Höhe eines Baumes wird errechnet aus dem 2er-logarithmus(n), wobei n die Anzahl der Elemente im binären Suchbaum darstellt. Anhand eines Beispiels zeigt sich was das bedeutet: Es existiert ein Baum mit 1024 Elementen darin. Die optimale Höhe beträgt daher 10. Damit findet man einen beliebigen Knoten, sonfern er sich im Baum befindet, im worst case nach 10 Entscheidungen. Vorraussetzung ist dafür dass dieser Baum die optimale Höhe besitzt und nicht etwa ein entarteter Baum ist. In diesem Fall eines entarteten Baumes wären es im worst case 1024 Entscheidungen, um einen sich im Baum befindenden Knoten zu finden.

Blatt

Als Blatt bezeichnet man einen Zeiger auf null. Oftmals spricht man auch von einem NIL-Zeiger. Ein Knoten n besitzt maximal zwei Söhne (im binären Suchbaum). Sein linker Sohn kann ein weiter Knoten sein, welcher aber einen kleineren Schlüssel/Key haben muss als sein Vorgänger. Der rechte Sohn kann unter Umständen so ein NIL-Zeiger sein, wenn der Zeiger des Knotens n auf den rechten Sohn auf NULL zeigt. Natürlich können beide oder auch kein Zeiger eines Knotens NIL-Zeiger sein.

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).

Algorthmus

 suche zu löschenden Knoten n
 wenn n nicht NULL
   n hat keinen Sohn:
     lösche Knoten n
   n hat einen Sohn:
     kopiere gesamten Sohn an die Stelle n
   n hat zwei Söhne
     suche symmetrischen Nachfolger m
     kopiere Daten (Schlüssel) nach n
     lösche symmetrischen Nachfolger

Symmetrischer Nachfolger

Als symmetrischen Nachfolger bezeichnet man den nächst-höheren Knoten des aktuellen Knotens.

Siehe auch

Wikisource: Binärer Suchbaum – Quellen und Volltexte

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