Kurs:Algorithmen und Datenstrukturen (hsrw)/Vorlesung/Binäre Suchbäume Weitere Aspekte

Weitere Aspekte

Die Komplexität der Operation hängt von der Höhe ab. Der Aufwand für die Höhe des Baumes beträgt O(h). Die Höhe eines ausgeglichenen binären Baumes ist h=ld(n) für Knoten. Bei eines ausgeglichenen oder balancierten Baum unterscheiden sich zum einen der rechte und linke Teilbaum eines jeden Knotens in der Höhe um höchstens 1 und zum anderen unterscheiden sich je zwei Wege von der Wurzel zu einem Blattknoten höchstens in um 1 in der Länge. Rot-Schwarz Bäume und AVL Bäume benötigen einen Ausgleich nach dem Einfügen und Löschen.

Entartung von Bäumen

Ungünstige Einfüge- oder Löschreihenfolge führt zu extremer Unbalanciertheit. Im Extremfall wird der Baum zur Liste, dann haben die Operationen eine Komplexität von O(n). Beispiel:

for (int i = 0; i < 10; i++)
tree.insert(i);

Vermeiden kann man dies durch spezielle Algorithmen zum Einfügen und Löschen, z.B. mit Rot-Schwarz-Bäumen und AVL-Bäumen.