Robert Sedgewick: Algorithmen

[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]


15. Ausgeglichene Bäume



Die auf binären Bäumen basierenden Algorithmen des vorangegangenen Kapitels sind für eine Vielzahl von Anwendungen sehr gut geeignet, doch tritt bei ihnen das Problem eines schlechten Verhaltens im ungünstigsten Fall auf. Hinzu kommt, daß es wie bei Quicksort der ungünstigste Fall in der Praxis mit einiger Wahrscheinlichkeit eintreten kann, wenn der Benutzer des Algorithmus keine Vorkehrungen dagegen trifft. Bereits geordnete Dateien, in umgekehrter Reihenfolge geordnete Dateien, Dateien mit sich abwechselnden großen und kleinen Schlüsseln oder Dateien, die einen großen Abschnitt mit einfacher Struktur enthalten, können bewirken, daß der Binärbaum-Suchalgorithmus sich sehr ungünstig verhält.

Im Falle von Quicksort bestand unser einziger Ausweg zur Verbesserung der Situation darin, Zuflucht zur Randomisierung zu suchen: Indem wir ein zufälliges zerlegendes Element auswählten, konnten wir uns auf die Gesetze der Stochastik verlassen, um uns vor dem ungünstigsten Fall zu schützen. Zum Glück gibt es bei der Suche im Binärbaum eine weit bessere Lösung: Es existiert eine allgemeine Technik, die uns die Möglichkeit gibt zu garantieren, daß dieser ungünstigste Fall nicht eintreten wird. Diese Technik, die Ausgleichen (balancing) genannt wird, wurde als Grundlage für verschiedene Algorithmen »auf ausgeglichenen Bäumen« benutzt. Wir werden einen derartigen Algorithmus eingehender untersuchen und kurz erörtern, in welcher Beziehung er zu einigen der anderen gebräuchlichen Verfahren steht.

Wie wir bald sehen werden, ist das Implementieren von Algorithmen auf ausgeglichenen Bäumen leichter gesagt als getan. Oft läßt sich die allgemeine Idee, die einem Algorithmus zugrunde liegt, leicht beschreiben, doch eine Implementation beinhaltet eine Unmenge von Spezial- und symmetrischen Fällen. Das im vorliegenden Kapitel entwickelte Programm ist nicht nur ein wichtiges Suchverfahren, sondern es verdeutlicht auch den Zusammenhang zwischen einer Beschreibung »auf hoher Ebene« und einem Pascal-Programm zur Implementation eines Algorithmus »auf niedriger Ebene«.


[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]