Robert Sedgewick: Algorithmen

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


Literatur für Suchen



Die wichtigsten Quellen für diesen Abschnitt sind der Band 3 von Knuth, sowie die Bücher von Gonnet und Mehlhorn. Die Mehrzahl der Algorithmen, die wir betrachtet haben, wird in diesen Büchern sehr ausführlich behandelt, mit mathematischen Analysen und Hinweisen für praktische Anwendungen. Klassische Verfahren werden bei Knuth betrachtet; die neueren Methoden werden von Gonnet und Mehlhorn beschrieben. Dort finden Sie auch weitere Literaturhinweise. Diese drei Bücher enthalten nahezu sämtliche »über den Rahmen dieses Buches hinausgehenden« Analysen, auf die in diesem Abschnitt verwiesen wurde.

Das in Kapitel 15 dargelegte Material entstammt der Arbeit von Guiba und Sedgewick von 1978, in der gezeigt wird, wie sich viele klassische Algorithmen, die ausgeglichene Bäume benutzen, in das Rot-schwarz-Schema einfügen lassen, und in der verschiedene weitere Implementationen angegeben werden. Es existiert eine sehr umfangreiche Literatur zu ausgeglichenen Bäumen; der daran interessierte Leser sollte mit der genannten Arbeit beginnen. Das Buch von Mehlhorn enthält ausführliche Beweise der Eigenschaften von Rot-Schwarzen Bäumen und ähnlichen Strukturen sowie Hinweise auf neuere Arbeiten. In dem Überblick von Comer von 1979 werden B-Bäume von einem eher praktischen Standpunkt aus behandelt.

Der in Kapitel 18 vorgestellte Algorithmus des erweiterbaren Hashing stammt aus der Arbeit von Fagin, Nievergelt, Pippenger und Strong von 1979. Diese Arbeit ist obligatorisch für jeden, der weitere Informationen zu externen Suchverfahren erhalten möchte; sie verknüpft Material aus unseren Kapiteln 16 und 17 zu dem Algorithmus aus Kapitel 18. Die Arbeit enthält außerdem eine gründliche Analyse sowie Betrachtungen zu damit zusammenhängenden praktischen Fragen.

Viele praktische Anwendungen der hier, insbesondere in Kapitel 18, betrachteten Methoden treten im Zusammenhang mit Datenbank-Systemen auf. Die Untersuchung von Datenbanken ist ein weites, in der Entwicklung begriffenes Feld, doch elementare Suchalgorithmen spielen in den meisten Systemen weiterhin eine fundamentale Rolle. Eine Einführung in dieses Gebiet gibt das Buch von Ullman von 1982.


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