Binärer Suchbaum
right|150px|thumb|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.
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:
