AVL- und Splay trees
Worum geht es hier?
Die höhere Effizienz unseres binaereSuche Algorithmus auf unseren binären Suchbäumen beruht zum wesentlichen auf deren Höhenbalance. Wenn diese verloren geht, wird die Laufzeit schlechter. Was passiert aber, wenn wir z.B. unsere Einfügeoperation nutzen und viel Pech haben (oder auch beim Löschen)?
Sehen wir uns doch ein Beispiel an:
Fügen wir jetzt unserem Algorithmus folgend in diesen Baum nacheinander die Knoten mit Schlüssel 40, 45 und 77 ein ergibt sich dieser Baum:
Die Höhe hat sich verdoppelt und die Worst-Case Laufzeit ist entsprechend extrem gestiegen. Ähnliche Probleme ergeben sich beim Löschen, wo die Worst-Case Laufzeit unter Umständen nicht entsprechend der sinkenden Anzahl der Knoten mit sinkt.
AVL und Splay trees sind Binärbäume mit entsprechend angepassten (etwas komplizierteren) add und delete Operationen, sie dieses Problem beheben.
Dies ist sowohl von Schwierigkeitsgrad als auch Umfang ein sehr gutes Thema für eine umfangreiche Ausarbeitung im Gebiet Informatik. Außerdem bezieht es sich direkt auf unsere Suchbäume und gibt so einen noch besseren Einblick in unser spezielles Thema, anstatt nur das Thema Bäume an sich.