Binärer Suchbaum

Ein binärer Suchbaum ist eine Datenstruktur. Es handelt sich um einen binären Baum mit der Eigenschaft, dass der linke Nachfolger eines Knotens einen kleineren Wert hat als der Knoten selbst, und der rechte Nachfolger einen größeren oder gleichen Wert.

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 durch, 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 des Wurzelknotens mit dem Suchschlüssel verglichen wird.

Ist er 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 er nicht kleiner, so wird entsprechend im rechten Teilbaum weitergesucht.

Bei vollständig gefüllten binären Suchbäumen ist die Suche in logarithmischer Laufzeit möglich (Aufwandsklasse O(log n)). Ist der Baum jedoch zu einer verketteten Liste entartet, so verschlechtert sich die Suche zu linearer Laufzeit (Aufwandsklasse O(n)).

Einfügen in binären Suchbäumen

Das Einfügen funktioniert nach dem gleichen Prinzip wie das Suchen.

Der Einfügealgorithmus beginnt bei der Wurzel; existiert diese nicht, d.h. ist der Baum leer, so wird das einzufügende Element als neue Wurzel gespeichert.

Andernfalls wird das einzufügende Element rekursiv entweder in den linken oder rechten Teilbaum der Wurzel eingefügt, je nachdem, ob sein Schlüssel kleiner als der Wert der Wurzel ist.

Die Komplexität entspricht der der Suchoperation.

Löschen in binären Suchbäumen

...