Eigenschaften binärer Suchbäume

1. Ordnung

Ein binärer Suchbaum kann als Implementierung einer Nachschlagetabelle dienen.

Unser Zweck bei der Verwendung eines binären Suchbaums ist, den Wert durch Nachschlagen des Schlüssels unmittelbar zu erhalten. Minimum, Maximum, Nachfolger, Vorgänger, Floor, Ceil, Rang (welches Element wo rangiert) und Select (welches Element das n-te ist) sind alles Ausprägungen der Ordnungseigenschaft von binären Suchbäumen.

2. Einschränkungen

Binäre Suchbäume haben Einschränkungen bei der zeitlichen Leistungsfähigkeit.

Wie in der folgenden Abbildung dargestellt, können mit denselben Elementknoten zwei verschiedene binäre Suchbäume gebildet werden, die beide die Definition erfüllen:

Ein binärer Suchbaum kann zu einer verketteten Liste entarten. Dementsprechend hängt die Suchoperation eines binären Suchbaums von der Höhe des Baums ab, und in diesem Fall ist die Höhe des Baums seine Knotenanzahl n. Gleichzeitig entarten alle entsprechenden Algorithmen des binären Suchbaums auf das O(n)-Niveau.