Robert Sedgewick: Algorithmen

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


4. Bäume



Die in
Kapitel 3 behandelten Strukturen sind ihrem Wesen nach eindimensional: Ein Element folgt dem anderen. Im vorliegenden Kapitel betrachten wir zweidimensionale verkettete Strukturen, die Bäume genannt werden und für viele unserer wichtigsten Algorithmen von zentraler Bedeutung sind. Eine vollständige Behandlung von Bäumen könnte ein ganzes Buch füllen, da sie in vielen Anwendungen außerhalb der Informatik auftreten und als mathematische Objekte gründlich untersucht worden sind. In der Tat könnte man sagen, daß dieses Buch eine Erörterung von Bäumen zum Gegenstand hat, denn diese sind auf grundsätzliche Weise in jedem seiner Abschnitte präsent. In diesem Kapitel betrachten wir die mit Bäumen zusammenhängenden grundlegenden Definitionen und die entsprechende Terminologie, untersuchen einige wichtige Eigenschaften und suchen nach Wegen ihrer Darstellung in einem Computer. In nachfolgenden Kapiteln werden wir viele Algorithmen kennenlernen, die auf diesen grundlegenden Datenstrukturen operieren.

Auf Bäume trifft man im alltäglichen Leben häufig, und der Leser ist gewiß mit dem Grundgedanken recht vertraut. Zum Beispiel forschen viele Leute nach ihren Vorfahren und/oder Nachkommen mit Hilfe eines Familienstammbaums. Wie wir sehen werden, entstammt ein großer Teil unserer Terminologie diesem Anwendungsbereich. Auf ein weiteres Beispiel stößt man bei der Organisation von Turnieren im Sport; diese Anwendung, mit der wir uns in Kapitel 11 beschäftigen werden, wurde von Lewis Carroll untersucht. Als ein drittes Beispiel kann das Schema der Organisation eines großen Unternehmens genannt werden; dieser Anwendungsfall kann als Anregung für die »hierarchische Zerlegung« dienen, die in der Informatik vielerorts Anwendung findet. Ein viertes Beispiel ist ein »Syntaxbaum«, der die Zerlegung eines Satzes in seine Bestandteile wiedergibt; dies hängt eng mit der Verarbeitung von Computersprachen zusammen, was wir später in Kapitel 21 untersuchen werden. Weitere Beispiele werden wir überall im Buch streifen.


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