Robert Sedgewick: Algorithmen

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


4. Bäume



Darstellung von Wäldern

Binäre Bäume besitzen zwei Verkettungen unterhalb jedes inneren Knotens, so daß die oben für sie benutzte Darstellung sich unmittelbar realisieren läßt. Doch wie verfahren wir bei allgemeinen Bäumen, oder Wäldern, in denen ein Knoten eine beliebige Anzahl von Verkettungen zu den Knoten weiter unten erfordern kann? Es zeigt sich, daß es zwei recht einfache Auswege aus diesem Dilemma gibt.

Erstens brauchen wir uns in vielen Anwendungen nicht im Baum abwärts zu bewegen, sondern nur aufwärts! In solchen Fällen benötigen wir nur eine Verkettung für jeden Knoten zu seinem direkten Vorgänger. Abbildung 4.6 zeigt diese Darstellung für den Baum in Abbildung 4.1: Das Feld a enthält die Information, die mit jedem Datensatz verknüpft ist, und das Feld dad enthält die Verkettungen zu den direkten Vorgängern. Folglich ist die Information, die mit dem direkten Vorgänger von a[i] verknüpft ist, in a[dad[i]] enthalten. Es wird vereinbart, daß die Wurzel auf sich selbst zeigt. Dies ist eine sehr kompakte Darstellung, die unbedingt zu empfehlen ist, wenn eine Bewegung im Baum aufwärts geeignet ist. In den Kapiteln 22 und 30 betrachten wir Anwendungsbeispiele für diese Darstellung.

Abbildung 4.6
Abbildung 4.6 Darstellung eines Baumes mit Hilfe von Verkettung zum direkten Vorgänger.

Um einen Wald für die Top-Down-Verarbeitung darzustellen, brauchen wir einen Weg zur Behandlung der direkten Nachfolger jedes Knotens ohne vorherige Zuweisung einer speziellen Zahl zu jedem Knoten. Doch dies ist gerade der Typ von Einschränkungen, für deren Beseitigung verkettete Listen geeignet sind. Es ist klar, daß wir für die direkten Nachfolger eines jeden Knotens eine verkettete Liste verwenden sollten. Dann umfaßt jeder Knoten zwei Verkettungen, eine für die verkettete Liste, die ihn mit seinen »Geschwistern« verbindet, und eine für die verkettete Liste seiner direkten Nachfolger. Abbildung 4.7 zeigt diese Darstellung für den Baum von Abbildung 4.1. Anstatt zum Beenden jeder Liste einen Pseudoknoten zu benutzen, lassen wir sie einfach zurück auf den direkten Vorgänger zeigen; dadurch ergibt sich eine Möglichkeit, sich im Baum ebenso aufwärts wie abwärts zu bewegen. (Diese Verkettungen können markiert werden, um sie von »Geschwister«-Verkettungen zu unterscheiden; alternativ kann auch der Vorgänger markiert oder sein Name abgespeichert werden, so daß, wenn seine direkten Nachfolger bearbeitet werden, die Bearbeitung abgebrochen wird, wenn dieser Vorgänger erreicht wurde.)

Abbildung 4.7
Abbildung 4.7 Darstellung eines Baumes mit Hilfe von Verkettung zum linken direkten Nachfolger und zum rechten »Bruder«.

In dieser Darstellung hat jedoch jeder Knoten genau zwei Verkettungen (eine zu seinem »Bruder« auf der rechten Seite und eine zu seinem direkten Nachfolger, der sich am weitesten links befindet). Man könnte daher fragen, ob ein Unterschied zwischen dieser Datenstruktur und einem binären Baum besteht. Die Antwort lautet »nein«, wie aus der Abbildung 4.8, der Darstellung des Baumes von Abbildung 4.1 als binärer Baum, ersichtlich ist. Das bedeutet, daß jeder Wald als ein binärer Baum dargestellt werden kann, indem man die linke Verkettung jedes Knotens auf den am weitesten links befindlicher direkter Nachfolger und rechte Verkettung, Darstellung von Wäldern>am weitesten links befindlichen direkten Nachfolger und die rechte Verkettung jedes Knotens auf seinen rechts von ihm angeordneten »Bruder« zeigen läßt. (Diese Tatsache ist anfangs oft überraschend.)

Abbildung 4.8
Abbildung 4.8 Darstellung eines Baumes als binärer Baum.

Daher können wir bei der Entwicklung von Algorithmen immer, wenn dies angemessen ist, auch Wälder benutzen. Wenn wir uns von unten aufwärts bewegen, lassen sich Wälder durch die Darstellung mit Verkettungen zum direkten Vorgänger einfacher behandeln als die meisten anderen Arten von Bäumen, und wenn wir uns von oben nach unten bewegen, sind sie dem Wesen nach äquivalent zu binären Bäumen.


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