Robert Sedgewick: Algorithmen

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


4. Bäume



Terminologie

Wir beginnen unsere Behandlung von Bäumen damit, daß wir sie als abstrakte Objekte definieren und die wesentlichen damit zusammenhängenden Begriffe einführen. Es gibt eine Reihe äquivalenter Wege der Definition von Bäumen, sowie eine Reihe von mathematischen Eigenschaften, welche diese Äquivalenz bewirken; diese werden im folgenden Abschnitt ausführlicher betrachtet.

Ein Baum ist eine nichtleere Menge von Knoten und Kanten, die gewissen Forderungen genügt. Ein Knoten ist ein einfaches Objekt, das einen Namen haben und andere mit ihm verknüpfte Informationen tragen kann; eine Kante ist eine Verbindung zwischen zwei Knoten. Ein Pfad in einem Baum ist eine Liste von unterschiedlichen Knoten, in welcher aufeinanderfolgende Knoten durch Kanten im Baum verbunden sind. Einer der Knoten im Baum wird als die Wurzel bezeichnet; die für die Definition entscheidende Eigenschaft eines Baumes ist, daß es zwischen der Wurzel und jedem beliebigen anderen Knoten im Baum genau einen Pfad gibt. Falls es zwischen der Wurzel und einem bestimmten Knoten mehr als einen Pfad gibt, oder falls es zwischen der Wurzel und einem bestimmten Knoten keinen Pfad gibt, so ist das, was vorliegt, ein allgemeiner Graph (siehe Kapitel 29) und kein Baum. Abbildung 4.1 zeigt ein Beispiel eines Baumes.

Obwohl die Definition keine »Richtung« für die Kanten festlegt, stellen wir uns normalerweise vor, daß die Kanten alle von der Wurzel weg (nach unten in Abbildung 4.1) oder - je nach Anwendungsfall - zur Wurzel hin zeigen (nach oben in Abbildung 4.1). Wir zeichnen Bäume gewöhnlich mit der Wurzel an der Spitze (auch wenn das zunächst unnatürlich erscheint), und wir sagen, daß der Knoten y sich unter dem Knoten x befindet (und x über y), wenn x auf dem Pfad von y zur Wurzel liegt (das heißt, wenn y beim Zeichnen des Baumes unterhalb von x angeordnet und mit x durch einen Pfad verbunden ist, welcher nicht über die Wurzel verläuft). Jeder Knoten (außer der Wurzel) besitzt genau einen Knoten, der sich unmittelbar über ihm befindet und als sein direkter Vorgänger (parent) bezeichnet wird; die Knoten unmittelbar unter einem Knoten werden seine direkten Nachfolger (children) genannt. Manchmal setzt man die Analogie zu Familienstammbäumen noch weiter fort und spricht vom »Großvater« oder von »Geschwistern« eines Knoten; in Abbildung 4.1 ist P das »Enkelkind« von R und hat drei »Geschwister«.

Abbildung 4.1
Abbildung 4.1 Beispiel eines Baumes.

Knoten ohne Nachfolger werden manchmal Blätter oder Endknoten genannt. In Analogie zur letzteren Bezeichnung werden Knoten mit wenigstens einem Nachfolger gelegentlich Nichtendknoten genannt. Endknoten unterscheiden sich oft von Nichtendknoten: Es ist zum Beispiel möglich, daß sie keinen Namen oder zugehörige Informationen besitzen. Besonders in solchen Situationen bezeichnen wir Nichtendknoten als innere Knoten und Endknoten als äußere Knoten.

Jeder Knoten ist die Wurzel eines Unterbaumes, welcher aus ihm und den Knoten unter ihm besteht. In dem Baum, der in Abbildung 4.1 dargestellt ist, gibt es sieben Unterbäume mit einem Knoten, einen Unterbaum mit drei Knoten, einen Unterbaum mit fünf Knoten und einen Unterbaum mit sechs Knoten. Eine Menge von Bäumen wird Wald genannt. Wenn wir zum Beispiel von dem Baum in Abbildung 4.1 die Wurzel und die mit ihr verbundenen Kanten entfernen, so bleibt ein Wald übrig, der aus drei Bäumen mit den Wurzeln A, R und E besteht.

Manchmal ist die Art, in der die Nachfolger eines jeden Knotens angeordnet sind, von Bedeutung, und manchmal ist dies nicht der Fall. Ein geordneter Baum ist ein Baum, in welchem die Reihenfolge der direkten Nachfolger bei jedem Knoten angegeben ist. Natürlich werden die Nachfolger in einer bestimmten Reihenfolge angeordnet, wenn wir einen Baum zeichnen, und es ist klar, daß es viele verschiedene Wege gibt, ungeordnete Bäume zu zeichnen. Wie wir später sehen werden, ist dies von Bedeutung, wenn wir Bäume in einem Computer darstellen wollen, da dort bezüglich der Art und Weise der Darstellung von geordneten Bäumen viel weniger Flexibilität vorhanden ist. Im Normalfall ist durch die Art der Anwendung offensichtlich, welcher Typ eines Baumes benötigt wird.

Die Knoten eines Baumes lassen sich in Ebenen (Stufen) einteilen. Die Ebene eines Knotens ist die Anzahl der Knoten auf dem Pfad von ihm zur Wurzel (ohne ihn selbst). Somit befindet sich zum Beispiel in Abbildung 4.1 R auf der Ebene 1 und S auf der Ebene 2. Die Höhe eines Baumes ist die höchste Ebene, die unter allen Knoten im Baum auftritt (oder der maximale Abstand zwischen irgendeinem Knoten und der Wurzel). Die Pfadlänge eines Baumes ist die Summe der Ebenen aller Knoten des Baumes (oder die Summe der Längen der Pfade von jedem Knoten zur Wurzel). Der Baum in Abbildung 4.1 hat die Höhe 3 und die Pfadlänge 21. Falls innere von äußeren Knoten unterschieden werden, so sprechen wir von innerer Pfadlänge und äußerer Pfadlänge.

Falls jeder Knoten eine bestimmte Anzahl von direkten Nachfolgern haben muß, die in einer bestimmten Reihenfolge erscheinen, so haben wir es mit einem n-ären Baum zu tun. In einem solchen Baum ist es zweckmäßig, spezielle äußere Knoten zu definieren, die keine Nachfolger haben (und gewöhnlich auch keinen Namen oder sonstige mit ihnen verknüpfte Informationen besitzen). Die äußeren Knoten spielen dann die Rolle von »Pseudoknoten«, als Bezeichnung für Knoten, die nicht die vorgeschriebene Anzahl von Nachfolgern besitzen.

Insbesondere ist der einfachste Typ eines n-ären Baumes der binäre Baum. Ein binärer Baum ist ein geordneter Baum, der aus zwei Typen von Knoten besteht: äußeren Knoten (ohne Nachfolger) und inneren Knoten mit genau zwei direkten Nachfolgern. Ein Beispiel eines binären Baumes zeigt Abbildung 4.2. Da die zwei direkten Nachfolger eines jeden inneren Knotens geordnet sind, sprechen wir vom linken und rechten Nachfolger innerer Knoten. Jeder innere Knoten muß sowohl einen linken als auch einen rechten Nachfolger haben, obwohl es sich bei einem oder beiden von ihnen um einen äußeren Knoten handeln kann.

Abbildung 4.2
Abbildung 4.2 Beispiel eines binären Baumes.

Der Zweck des binären Baumes besteht in der Strukturierung der inneren Knoten; die äußeren Knoten dienen lediglich als Platzhalter. Wir schließen sie in die Definition mit ein, weil die am häufigsten verwendeten Darstellungen binärer Bäume jeden äußeren Knoten berücksichtigen müssen. Ein binärer Baum ist »leer«, wenn er nur aus einem äußeren Knoten und keinem inneren Knoten besteht.

Ein voller binärer Baum ist ein binärer Baum, in welchem jede Ebene völlig mit inneren Knoten ausgefüllt ist, eventuell mit Ausnahme der letzten Ebene. Ein vollständiger binärer Baum ist ein voller binärer Baum, bei dem alle inneren Knoten der untersten Ebene links von den äußeren Knoten dieser Ebene erscheinen. Abbildung 4.3 zeigt ein Beispiel eines vollständigen binären Baumes. Wie wir sehen werden, finden binäre Bäume in der Informatik breite Anwendung, und die Effizienz ist dann am höchsten, wenn sie voll (oder nahezu voll) sind. In Kapitel 11 werden wir eine wichtige Datenstruktur untersuchen, die auf vollständigen binären Bäumen beruht.

Abbildung 4.3
Abbildung 4.3 Ein vollständiger binärer Baum.

Der Leser sollte beachten, daß zwar jeder binäre Baum ein Baum, aber nicht jeder Baum ein binärer Baum ist. Selbst wenn man nur geordnete Bäume betrachtet, in denen jeder Knoten keinen, einen oder zwei direkte Nachfolger hat, könnte jeder derartige Baum vielen binären Bäumen entsprechen, da Knoten mit einem direkten Nachfolger entweder links oder rechts in einem binären Baum sein könnten.

Wie wir im folgenden Kapitel sehen werden, hängen Bäume sehr eng mit Rekursion zusammen. Der vielleicht einfachste Weg, Bäume zu definieren, besteht in der rekursiven Definition folgender Art: »Ein Baum ist entweder ein einzelner Knoten oder ein als Wurzel dienender Knoten, der mit einer Menge von Bäumen verbunden ist«, und »Ein binärer Baum ist entweder ein äußerer Knoten oder ein als Wurzel dienender (innerer) Knoten, der mit einem linken binären Baum und einem rechten binären Baum verbunden ist.«


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