Robert Sedgewick: Algorithmen

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


4. Bäume



Eigenschaften

Bevor wir Darstellungsweisen behandeln, fahren wir im Stil einer mathematischen Abhandlung fort und betrachten eine Reihe wichtiger Eigenschaften von Bäumen. Auch hier könnte man wieder eine große Zahl von möglichen Eigenschaften betrachten; unser Ziel ist es, auf jene einzugehen, die für die Algorithmen, die später in diesem Buch dargelegt werden sollen, von besonderer Bedeutung sind.

Eigenschaft 4.1 Für je zwei beliebige Knoten in einem Baum existiert genau ein Pfad, der sie verbindet.

Zwei beliebige Knoten besitzen einen letzten gemeinsamen Vorgänger: einen Knoten, der auf dem Pfad von beiden Knoten zur Wurzel liegt, von dessen Nachfolgern jedoch keiner die gleiche Eigenschaft hat. Zum Beispiel ist O der letzte gemeinsame Vorgänger von C und L in dem Baum von Abbildung 4.3. Der letzte gemeinsame Vorgänger muß stets existieren, da entweder die Wurzel der letzte gemeinsame Vorgänger ist, oder beide Knoten sich in dem Unterbaum befinden, dessen Wurzel einer der direkten Nachfolger der Wurzel ist; in letzterem Falle ist entweder dieser Knoten der letzte gemeinsame Vorgänger, oder beide Knoten befinden sich in dem Unterbaum, dessen Wurzel einer von seinen direkten Nachfolgern ist, usw. Es gibt einen Pfad von jedem der Knoten zu dem letzten gemeinsamen Vorgänger; wenn man diese beiden Pfade zusammensetzt, erhält man einen Pfad, der die beiden Knoten verbindet. w.z.b.w.

Eine wichtige Folgerung aus Eigenschaft 4.1 besteht darin, daß jeder beliebige Knoten die Wurzel sein kann: Jeder Knoten in einem Baum hat die Eigenschaft, daß es genau einen Pfad gibt, der diesen Knoten mit jedem anderen Knoten im Baum verbindet. Technisch bezieht sich unsere Definition, in welcher die Wurzel festgelegt ist, auf einen Baum mit Wurzel oder orientierten Baum; ein Baum, in welchem die Wurzel nicht festgelegt ist, wird ein freier Baum genannt. Der Leser braucht sich wegen dieser Unterscheidung keine Gedanken zu machen; die Wurzel ist entweder festgelegt oder nicht.

Eigenschaft 4.2 Ein Baum mit N Knoten hat N - 1 Kanten.

Diese Eigenschaft folgt unmittelbar aus der Beobachtung, daß jeder Knoten (mit Ausnahme der Wurzel) einen einzigen direkten Vorgänger hat, und daß jede Kante einen bestimmten Knoten mit seinem direkten Vorgänger verbindet. Wir können diese Tatsache auch mittels Induktion anhand der rekursiven Defintion beweisen. w.z.b.w.

Die nächsten beiden Eigenschaften, die wir betrachten wollen, beziehen sich auf binäre Bäume. Wie bereits erwähnt, treten diese Strukturen im vorliegenden Buch häufig auf, so daß es sich lohnt, ihren Merkmalen einige Aufmerksamkeit zu schenken. Hierdurch wird die Grundlage für das Verständnis der Merkmale der Leistungsfähigkeit verschiedener Algorithmen gelegt, mit denen wir uns beschäftigen werden.

Eigenschaft 4.3 Ein binärer Baum mit N inneren Knoten hat N + 1 äußere Knoten.

Diese Eigenschaft kann durch vollständige Induktion bewiesen werden. Ein binärer Baum, der keine inneren Knoten hat, hat einen äußeren Knoten, so daß die Eigenschaft für N = 0 gilt. Für N > 0 hat jeder binäre Baum mit N inneren Knoten k innere Knoten in seinem linken und N - 1 - k innere Knoten in seinem rechten Unterbaum für ein gewisses k zwischen 0 und N - 1, da die Wurzel ein innerer Knoten ist. Aufgrund der Induktionsannahme hat der linke Unterbaum k + 1 und der rechte Unterbaum N - k äußere Knoten, was zusammen N + 1 ergibt. w.z.b.w.

Eigenschaft 4.4 Die äußere Pfadlänge eines beliebigen binären Baumes mit N inneren Knoten ist um 2N größer als die innere Pfadlänge.

Diese Eigenschaft kann ebenfalls durch vollständige Induktion bewiesen werden, doch ist ein anders gearteter Beweis gleichfalls lehrreich. Wir beachten dazu, daß jeder binäre Baum mit Hilfe des folgenden Prozesses konstruiert werden kann: Man beginne mit dem binären Baum, der aus einem äußeren Knoten besteht. Dann wiederhole man N mal die folgenden Schritte: Man wähle einen äußeren Knoten und ersetze ihn durch einen neuen inneren Knoten mit zwei äußeren Knoten als direkten Nachfolgern. Wenn der gewählte äußere Knoten sich auf der Ebene k befindet, erhöht sich die innere Pfadlänge um k, die äußere Pfadlänge dagegen um k + 2 (ein äußerer Knoten auf der Ebene k wird entfernt, jedoch werden zwei auf der Ebene k + 1 hinzugefügt). Der Prozeß beginnt mit einem Baum, für den sowohl die innere als auch die äußere Pfadlänge den Wert 0 haben, und N Schritte lang erhöht sich die äußere Pfadlänge jeweils um 2 mehr als die innere Pfadlänge. w.z.b.w.

Schließlich betrachten wir noch einfache Eigenschaften der »besten« Art binärer Bäume, sog. voller Bäume. Diese Bäume sind von Interesse, weil ihre Höhe garantiert gering ist, so daß es niemals sehr aufwendig ist, von der Wurzel zu irgendeinem Knoten oder umgekehrt zu gelangen.

Eigenschaft 4.5 Die Höhe eines vollen binären Baumes mit N inneren Knoten beträgt etwa log2N.

Aus Abbildung 4.3 ist ersichtlich, daß, wenn die Höhe N beträgt, gelten muß

2N-1 < N + 1 <= 2N,

da N + 1 äußere Knoten existieren. Hieraus folgt die Gültigkeit der formulierten Eigenschaft. (In Wirklichkeit ist die Höhe exakt gleich log2N, aufgerundet auf die Nächste ganze Zahl, doch wir wollen darauf verzichten, so genau zu sein, was in Kapitel 6 erläutert wird.) w.z.b.w.

Weitere mathematische Eigenschaften von Bäumen werden wir in den folgenden Kapiteln nach Bedarf erörtern. An dieser Stelle sind wir nunmehr in der Lage, uns der praktischen Frage zuzuwenden, wie man Bäume im Computer darstellen und sie effizient handhaben kann.


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