14.4Ausgeglichene Bäume

Wie kann nun verhindert werden, dass ein Suchbaum bei einer »ungünstigen« Einfügereihenfolge entartet? Grundsätzlich kann man versuchen, den Baum nach jeder Einfüge- und Löschoperation auszugleichen. Dies kann jedoch zur Folge haben, dass unter Umständen jeder Knoten bewegt werden muss, wie dies in Abbildung 14–12 für das Einfügen des Elementes »1« dargestellt ist.

Wir werden im Folgenden drei Lösungsideen vorstellen, die dieses Problem vermeiden:

Abb. 14–12 Vollständiges Ausgleichen eines Baumes

Rot-Schwarz-Bäume

• Rot-Schwarz-Bäume umgehen aufwendige Strukturänderungen zur Wiederherstellung der Ausgeglichenheit, indem sie mehr Flexibilität beim Einfügen durch Knoten mit mehr als einem Schlüssel zulassen.

AVL-Bäume

• AVL-Bäume basieren auf einem abgeschwächten Kriterium für eine ausgeglichene Höhe.

B-Bäume

• B-Bäume besitzen eine ausgeglichene Höhe, lassen aber einen unausgeglichenen Verzweigungsgrad zu.

Rot-Schwarz- und AVL-Bäume werden in vielen Lehrbüchern zu Datenstrukturen behandelt und sind daher die wohl bekanntesten Beispiele für ausgeglichene Bäume. Sie garantieren insbesondere die oben bereits erwähnte Höhenbeschränkung auf O(log n) bei n Knoten. B-Bäume kommen (in teilweise modifizierter Form) speziell in Datenbanksystemen als Indexstrukturen zum Einsatz.

14.4.1Rot-Schwarz-Bäume

Flexibilität bei der Schlüsselanzahl

Ein Ansatz zur Vermeidung der Entartung von Suchbäumen beim Einfügen ist eine größere Flexibilität bezüglich der Anzahl der Schlüssel pro Knoten: Erlaubt man mehr als einen Schlüssel (und damit mehr als zwei Nachfolger), lassen sich Strukturänderungen auf einen engen Bereich des Baumes beschränken, was wiederum den Aufwand für das Ausgleichen reduziert.

2-3-4-Bäume

Knotenarten

Dies führt zunächst zur Idee des 2-3-4-Baumes, der neben den einfachen Knoten des Binärbaumes (sogenannte 2-Knoten) auch 3-Knoten (mit drei Nachfolgern bzw. zwei Schlüsseln) und 4-Knoten (mit vier Nachfolgern bzw. drei Schlüsseln) erlaubt. Für die 3- und 4-Knoten gilt, dass die Schlüssel jeweils geordnet sind, so dass die Kante zwischen zwei Schlüsseln auf einen Teilbaum mit Werten verweist, die zwischen den beiden Schlüsseln liegen. Abbildung 14–13 zeigt ein Beispiel eines solchen Baumes, wobei die leeren Verweise zur Verdeutlichung der Anzahl der Nachfolger als kleine Quadrate dargestellt sind.

Abb. 14–13 2-3-4-Baum

Suchen
Teilen von Knoten
Bottom up vs. top down

Die Suche in einem 2-3-4-Baum erfolgt im Prinzip wie in einem Binärbaum, wobei der gesuchte Schlüssel natürlich bei 3- und 4-Knoten mit allen Schlüsselwerten des Knotens verglichen und die Suche gegebenenfalls im entsprechenden Teilbaum fortgesetzt werden muss. Interessanter ist das Einfügen: Zunächst muss wieder durch eine (erfolglose) Suche die Einfügeposition im Baum ermittelt werden. Handelt es sich dabei um einen 2- oder einen 3-Blattknoten, so kann dieser einfach um das neue Element erweitert werden. Ein 4-Knoten kann dagegen keine weiteren Elemente aufnehmen und muss daher geteilt werden. Dies erfolgt, indem aus dem 4-Knoten zwei 2-Knoten gebildet werden und das mittlere Schlüsselelement zum Vaterknoten verschoben wird. Sofern der Vaterknoten wiederum ein 4-Knoten ist, muss auch dieser geteilt werden usw. Günstiger als ein solcher Bottom-up-Ansatz ist hier ein Top-down-Vorgehen: Bei einer Einfügeoperation werden auf dem Weg von der Wurzel bis zur Einfügeposition einfach alle besuchten 4-Knoten vorsorglich in 2-Knoten aufgeteilt. Somit erfolgt das Ausgleichen automatisch, d.h., außer dem Aufsplitten der 4-Knoten sind beim Einfügen keine weiteren Vorkehrungen zu treffen! Darüber hinaus weisen 2-3-4-Bäume noch eine weitere positive Eigenschaft auf: Sofern alle Blattknoten auf derselben Stufe (Niveau) liegen, müssen beim Suchen in einem Baum mit n Knoten maximal log₂(n + 1) Knoten besucht werden.

Struktur von Rot-Schwarz-Bäumen

Binäre Repräsentation von 2-3-4-Bäumen

Obwohl das »automatische« Ausgleichen beim 2-3-4-Baum sehr angenehm ist, erweist sich die Verwaltung von Knoten mit unterschiedlicher Schlüsselanzahl doch als recht umständlich. Man kann aber 2-3-4-Bäume auch als gewöhnliche Binärbäume (d.h. nur mit 2-Knoten) darstellen. Dazu werden die 3- und 4-Knoten einfach durch kleine Binärbäume repräsentiert, deren verbindende Kanten rot markiert werden, während die Kanten des ursprünglichen 2-3-4-Baumes schwarz sind. Ein solcher Baum wird als Rot-Schwarz-Baum bezeichnet. Die Repräsentation von 3- bzw. 4-Knoten in einem solchen Baum ist in Abbildung 14–14 illustriert.

Abb. 14–14 Repräsentation von 3-und 4-Knoten im Rot-Schwarz-Baum

Da die »Farbe« einer Kante im Knoten gespeichert werden muss (z.B. als Bitwert) und damit ein Knoten die Farbe der Kante zu seinem Elternknoten annimmt, kann man auch von roten und schwarzen Knoten sprechen. Daher sind in Abbildung 14–14 sowie in den folgenden Beispielen die Knoten auch entsprechend markiert: Schwarze Knoten sind grau hinterlegt, rote Knoten sind weiß. Ein Rot-Schwarz-Baum ist somit wie folgt definiert:

Definition 14.1 Rot-Schwarz-Baum

Ein Rot-Schwarz-Baum ist ein binärer Suchbaum, der folgende Kriterien – die sogenannten Rot-Schwarz-Eigenschaften – erfüllt:

1. Jeder Knoten ist entweder rot oder schwarz.
2. Jeder Blattknoten (Null-Knoten) ist per Definition schwarz.
3. Die Kinder jedes roten Knotens sind schwarz.
4. Für jeden Knoten k gilt: Jeder Pfad von k zu einem Blatt enthält die gleiche Anzahl schwarze Knoten.

Da es sich somit um einen binären Baum handelt, lassen sich einige der Grundoperationen aus Abschnitt 14.3 direkt übernehmen. Insbesondere die Such- und Traversierungsmethoden sind ohne Änderung anwendbar – der Farbwert der Knoten wird einfach ignoriert.

Einfügen

Dagegen ist das Einfügen in einen Rot-Schwarz-Baum etwas komplizierter, weil die Einhaltung der Rot-Schwarz-Eigenschaften gewährleistet werden muss. Dies wird wie im 2-3-4-Baum durch Splitten der – hier virtuellen – 4-Knoten erreicht. Wie oben bereits angesprochen kann dies bottom-up (durch »normales« Einfügen wie im binären Suchbaum und anschließendes Splitten der 4-Knoten aufwärts) oder top-down (Splitten aller besuchten 4-Knoten auf dem Weg von der Wurzel bis zur Einfügeposition) erfolgen. Im Folgenden beschränken wir uns wieder auf die nichtrekursive Top-down-Variante.

Beim Durchwandern des Baumes von der Wurzel bis zur Einfügeposition müssen also alle 4-Knoten, d.h. Knoten, deren beide Kinder rot sind, gesplittet werden. Hierbei sind zwei Hauptfälle zu unterscheiden:

1. der 4-Knoten hängt an einem 2-Knoten,
2. der 4-Knoten hängt an einem 3-Knoten.

Umfärben

Fall 1 ist in Abbildung 14–15 sowohl in der 2-3-4-Baum-Variante als auch in Rot-Schwarz-Notation dargestellt. Wie aus der 2-3-4-Baum-Notation ersichtlich, erfolgt das Auflösen durch Umwandlung des Elternknotens in einen 3-Knoten. Im Rot-Schwarz-Baum entspricht dies einem einfachen Umfärben der Knoten. Der dazu symmetrische Fall (der 4-Knoten ist rechtes Kind) kann auf gleiche Weise behandelt werden. Die relevanten Knoten sind mit »n« (für den aktuell betrachteten Knoten), »p« (für dessen Elternknoten – parent) und »g« (für den Elternknoten von p – grandparent) bezeichnet, die anderen beteiligten Knoten sind mit v, w, x, y benannt.

Abb. 14–15 Fall 1 des Splittens im Rot-Schwarz-Baum

Fall 2 kann entsprechend der Kantenanzahl des Elternknotens in drei Varianten auftreten, wobei jedoch zwei davon symmetrisch zueinander sind. Die erste Variante (mit Fall 2A bezeichnet) ist in Abbildung 14–16 dargestellt: Der 4-Knoten ist an einer der äußeren Kanten des Elternknotens angehängt. Das Ausgleichen erfolgt hier in zwei Schritten. Zunächst wird wieder das Umfärben der Knoten durchgeführt. Da danach zwei rote Knoten aufeinander folgen, muss anschließend durch eine Rotation Rotation wieder die Rot-Schwarz-Eigenschaft hergestellt werden. Eine Rotation ist dabei eine Strukturtransformation des Baumes (d.h. eine Vertauschung von Knoten), die jedoch die Sortierung der Knoten beibehält. Der Effekt dieser Operation ist in Abbildung 14–16 illustriert.

Abb. 14–16 Fall 2A des Splittens

Doppelrotation

In der zweiten Variante von Fall 2 (Fall 2B) ist der 4-Knoten das mittlere Kind seines Elternknotens. Die Behandlung dieses Falls erfordert eine Doppelrotation. Ein Beispiel für diese Situation ist in Abbildung 14–17 angegeben. Dabei sollte der Unterschied zu Fall 2A deutlich werden: Während dort der 4-Knoten und sein Elternknoten Kinder gleichen Typs waren (also entweder linke oder rechte Kinder im Rot-Schwarz-Baum), weisen sie im Fall 2B verschiedene Typen auf. Die erste Rotation überführt den Teilbaum somit zunächst in die Form von Fall 2A und behandelt diesen dann wie oben beschrieben durch eine weitere Rotation.

Für eine Implementierung des Rot-Schwarz-Baumes muss zunächst wieder eine eigene Knotenklasse RBNode definiert werden. Dies könnte durch Spezialisierung der Klasse TreeNode aus Programm 14.1 erfolgen, indem ein Attribut red hinzugefügt wird. Die vererbten Zugriffsmethoden getLeft bzw. getRight liefern jedoch weiterhin jeweils Objekte der Klasse TreeNode, so dass diese in den Rot-Schwarz-Baum-spezifischen Methoden in Instanzen von RBTree konvertiert werden müssten. Da dies die Lesbarkeit erschwert, definieren wir im Folgenden eine eigene Klasse. Die nicht dargestellten Methoden zur Initialisierung (d.h. der Konstruktor) sowie die Suchmethode entsprechen den Methoden der Klasse BinaryTree.

Abb. 14–17 Fall 2B des Splittens

Programm 14.9 Knotenklasse für RedBlackTree

In Programm 14.10 ist die Implementierung der neuen insert-Methode dargestellt, die an die in [Sed02a] vorgeschlagene Variante angelehnt ist. Zunächst wird durch die Binärbaum-Suche die Einfügeposition ermittelt. Dabei werden auch jeweils der Elternknoten (parent), der Großvater (grand für »grandparent«) und auch dessen Vorfahren (great für »great-grandparent«) in den entsprechenden Variablen vermerkt. Für jeden besuchten Knoten node wird außerdem geprüft, ob seine Kindknoten rot sind, d.h., ob es sich um einen 4-Knoten handelt. In diesem Fall wird der Knoten durch Aufruf der Methode split geteilt. Ist die Einfügeposition erreicht (der aktuelle Knoten ist ein Null-Knoten), so wird ein neuer Knoten erzeugt und in Abhängigkeit vom einzufügenden Wert als linkes oder rechtes Kind an den parent-Knoten (den untersten Nicht-Null-Knoten) angehängt. Eingefügte Knoten werden immer als Teil eines 4-Knotens angenommen, so dass für diese ebenfalls ein Split durchzuführen ist.

Programm 14.10 Einfügen im Rot-Schwarz-Baum

Split-Operation

Die Split-Operation wird ebenfalls durch eine eigene Methode split realisiert, die als Parameter das einzufügende Element sowie den zu teilenden Knoten und dessen Vorfahren benötigt (Programm 14.11). In dieser Methode wird im ersten Schritt das Umfärben durchgeführt (Fall 1). Danach wird geprüft, ob der Elternknoten ein 3-Knoten ist, d.h., ob der parent-Knoten rot ist. Wenn dies zutrifft (Fall 2), so wird zunächst untersucht, ob der aktuelle Knoten node und dessen Elternknoten gleich orientiert sind, also beide entweder linke oder rechte Kinder sind. Dies kann einfach durch Vergleich der jeweiligen Vorfahren mit dem Einfügewert realisiert werden: Sind beide entweder kleiner oder größer (die compareKeyTo-Methodenaufrufe liefern den gleichen Wert), dann sind beide Knoten gleich orientiert. Andernfalls ist Fall 2B eingetreten, der durch eine zusätzliche Rotation in Fall 2A überführt werden muss. Anschließend wird durch eine weitere Rotation Fall 2A behandelt. Der letzte Schritt ist das »Schwärzen« des geteilten Knotens sowie des Wurzelknotens für den Fall, dass dieser zuvor als 4-Knoten behandelt und deshalb rot gefärbt wurde. Da dies eigentlich nicht notwendig ist, wird die Farbe ohne Test auf Schwarz gesetzt.

Programm 14.11 Splitten von 4-Knoten im Rot-Schwarz-Baum

Als letzte Methode wird noch die rotate-Operation benötigt. Grundsätzlich könnten dabei die einzelnen Varianten der Rotation nach links bzw. rechts bzw. mit gleicher oder verschiedener Orientierung durch eine Fallunterscheidung behandelt werden. Eleganter ist jedoch die Lösung aus [Sed02a], wobei die für die Rotation benötigten Nachfolgerknoten anhand des Suchschlüssels wiedergefunden werden (Programm 14.12).

Programm 14.12 Rotation im Rot-Schwarz-Baum

Betrachten wir die Wirkungsweise der vorgestellten Methoden anhand eines Beispiels. Gegeben sei der Rot-Schwarz-Baum aus Abbildung 14–18, in den der Wert »13« eingefügt werden soll, wobei die (schwarzen) Null-Knoten (Blätter) aus Gründen der Übersichtlichkeit nicht mehr dargestellt sind.

Abb. 14–18 Einfügen im Rot-Schwarz-Baum: Beispiel

Bei der Suche nach der Einfügeposition wird der Baum zunächst bis zum Knoten »11« durchlaufen, der aufgrund seiner roten Kinder als 4-Knoten identifiziert wird. Daher wird die split-Methode für diesen Knoten aufgerufen, wobei die Parameter wie in Abbildung 14–18 dargestellt belegt sind. Der erste Schritt ist das Umfärben des node-Knotens sowie seiner Kinder. Da die Kanten zu parent bzw. zu grand unterschiedlich orientiert sind, muss eine Doppelrotation durchgeführt werden. Hier wird zunächst der Knoten »11« über den Knoten »9« nach oben gezogen und im zweiten Schritt schließlich noch über den Knoten »14«. Danach kann der neue Knoten »13« eingefügt werden. Nach dem abschließenden Schwärzen ergibt sich die Situation in Abbildung 14–19, wobei nur der relevante Teil des Baumes dargestellt ist.

Abb. 14–19 Rotationen beim Einfügen von »13«

Die Löschoperation im Rot-Schwarz-Baum kann im Prinzip auf ähnliche Weise wie das Einfügen realisiert werden. Auch hier bieten sich wieder sowohl die Bottom-up- als auch die Top-down-Variante an, wobei beim Top-down-Ansatz der Baum so umstrukturiert wird, dass der zu löschende Knoten rot wird, da der Knoten dann einfach entfernt werden kann [Wei98].

Rot-Schwarz-Bäume stellen eine interessante Variante von ausgeglichenen Bäumen dar. Eine wesentliche Eigenschaft ist dabei das Verhalten im ungünstigsten Fall, der eintritt, wenn auf dem Pfad von der Wurzel zu einem Blatt abwechselnd rote und schwarze Knoten liegen. In diesem Fall sind maximal 2 log₂(n + 1) Vergleiche notwendig gegenüber dem günstigsten Fall von log₂(n + 1) bei ausschließlich schwarzen Knoten. Interessant ist dabei insbesondere, dass dieses Verhalten mit geringem Aufwand (einige wenige lokale Rotationen) erreicht wird.

14.4.2AVL-Bäume

AVL-Bäume sind eine weitere Form von binären Suchbäumen, die das Entarten vermeiden und dabei den Aufwand beim Ausgleichen begrenzt halten. Die Bezeichnung AVL hat ihren Ursprung in den Namen der »Erfinder« dieser Datenstruktur, den russischen Mathematikern G. M. Adelson-Velskii und E. M. Landis. Ein binärer Suchbaum ist ein AVL-Baum, wenn das AVL-Kriterium erfüllt ist:

Definition 14.2 AVL-Kriterium

Für jeden (inneren) Knoten ist der absolute Betrag der Differenz der Höhen des linken und rechten Teilbaumes maximal 1.

Es sei angemerkt, dass es nicht genügt, dieses Kriterium nur für die Wurzel zu fordern, da beide Teilbäume der Wurzel entartet sein können. In Abbildung 14–20 ist die AVL-Eigenschaft verdeutlicht. Im linken Beispiel ist die Eigenschaft für jeden Teilbaum erfüllt, dagegen verletzen im rechten Beispiel die beiden Teilbäume der Wurzel die Forderung nach einer maximalen Höhendifferenz von 1.

Abb. 14–20 AVL-Eigenschaft am Beispiel

Während die Suchoperation für den AVL-Baum unverändert vom binären Suchbaum übernommen werden kann, erfordern die Manipulationsoperationen »Einfügen« und »Löschen« spezielle Vorkehrungen zur Erhaltung der AVL-Eigenschaft. Diese Operationen werden daher nachfolgend eingehender betrachtet.

Einfügen in AVL-Bäumen

Balance

Das grundsätzliche Vorgehen beim Einfügen eines Elementes entspricht dem Algorithmus vom binären Suchbaum: Die Position im Baum wird durch Vergleiche der Schlüssel ermittelt und der neue Knoten wird als Blatt angefügt. Als Folge dieser Operation kann jedoch die AVL-Eigenschaft verletzt sein. Bezeichnet man die Differenz der Höhen der Teilbäume left und right eines Knotens k als Balance b (k) mit

b(k) = height (right)− height (left)

so gilt für die AVL-Eigenschaft:

b(k) ∊ {− 1, 0, +1}

Nach dem Einfügen eines neuen Knotens kann die Balance auch die Werte − 2 und +2 annehmen:

b(k) ∊ {− 2, −1, 0, +1, +2}

Diese Verletzung der AVL-Eigenschaft muss nun durch Ausgleichen behoben werden. Da hierbei Knoten vertauscht werden müssen, ist eine Rotation notwendig.

Es lassen sich folgende Fälle identifizieren, die zu einer Verletzung der AVL-Eigenschaft führen können:

1. Einfügen in linken Teilbaum des linken Kindes
2. Einfügen in rechten Teilbaum des linken Kindes
3. Einfügen in rechten Teilbaum des rechten Kindes
4. Einfügen in linken Teilbaum des rechten Kindes

Hierbei sind die Fälle (1) und (3) sowie (2) und (4) symmetrisch und können daher in der gleichen Weise behandelt werden.

Abb. 14–21 Einfache Rotation

Für das Ausgleichen wird ausgehend vom eingefügten Knoten k₀ein Knoten k₁ auf dem Pfad zur Wurzel gesucht, dessen Großvater k₃ als erster unbalanciert ist, d.h. b(k₃) ∊ {− 2, +2}. Dabei kann durchaus k₁ = k₀ sein. Der Vaterknoten von k₁ wird entsprechend als k₂ bezeichnet. In Abbildung 14–21 ist dies für Fall (1) dargestellt: Die Balance für Knoten k₃ verletzt hier mit dem Wert − 2 die AVL-Eigenschaft. Der Teilbaum mit der Wurzel k₃ kann nun durch einfache Rotation von Knoten k₂ über k₃ ausgeglichen werden, so dass sich die neue Struktur mit k₂ als Wurzel und k₁ als linkes bzw. k₃ als rechtes Kind ergibt. Für Fall (3) erfolgt dies in analoger (spiegelbildlicher) Weise, d.h., hierbei werden k₃ linkes Kind und k₁ rechtes Kind von k₂.

Doppelrotation

Der Fall (2) erfordert dagegen eine Doppelrotation (Abbildung 14–22), da hier im rechten Teilbaum des linken Kindes bzw. im linken Teilbaum des rechten Kindes eingefügt wurde. Hier muss der Knoten k₁ Wurzel des ausgeglichenen Teilbaumes werden, da dessen Schlüssel zwischen k₂ und k₃ liegt. Die Bezeichnung »Doppelrotation« lässt sich durch das Rotieren von k₁ über k₂ und k₃ erklären. Für den Fall (4) erfolgt diese Operation wieder in spiegelbildlicher Weise. Zusammenfassend können wir für das Ausgleichen nach dem Einfügen folgende Regeln formulieren:

• Einfügen in linken Teilbaum des linken Kindes → Rotation mit linkem Kind

Abb. 14–22 Doppelrotation

• Einfügen in rechten Teilbaum des linken Kindes → Doppelrotation mit linkem Kind
• Einfügen in rechten Teilbaum des rechten Kindes → Rotation mit rechtem Kind
• Einfügen in linken Teilbaum des rechten Kindes → Doppelrotation mit rechtem Kind

Beispiel 14.1 Rotationen im AVL-Baum

Ausgehend von einem leeren Baum sollen folgende Elemente in der angegebenen Reihenfolge eingefügt werden. Die dabei notwendigen Schritte und Rotationen sind jeweils beschrieben und in Abbildung 14–23 dargestellt:

1. Einfügen von 3, 2, 1
   Mit dem Einfügen des dritten Elementes wird die AVL-Eigenschaft der Wurzel verletzt. Eine einfache Rotation (in der Abbildung mit »R« gekennzeichnet) nach rechts von 2 über 3 – im Weiteren notiert als (2, 3) – stellt die Ausgeglichenheit wieder her.
2. Einfügen von 4, 5
   Danach ist eine einfache Links-Rotation (4,3) notwendig.
3. Einfügen von 6
   Durch eine einfache Rotation nach links (4,2) wird der Baum wieder ausgeglichen.
4. Einfügen von 7
   Dies erfordert eine einfache Rotation nach links (6,5).
5. Einfügen von 16, 15
   An dieser Stelle ist eine Doppelrotation nach links (7,15,16) auszuführen (in der Abbildung mit »DR« gekennzeichnet).

Implementierung in Java

Zur Implementierung des AVL-Baumes in Java ist es zunächst sinnvoll, wieder eine eigene Knotenklasse AVLNode zu definieren, um so den Grad der Ausgeglichenheit (Balance) vermerken zu können. Dies erfolgt, wie bereits auf Seite 398 im Rahmen des Rot-Schwarz-Baumes diskutiert, durch eine neue Klasse und die einfache Übernahme der Methode aus TreeNode. Entsprechend wird für die Klasse AVLNode zusätzlich ein Attribut balance eingeführt, das die Werte 0, 1 und -1 annehmen kann.

Abb. 14–23 Ergebnis der Rotationen aus Beispiel 14.1

Programm 14.13 Knotenklasse für den AVL-Baum

Einfügen
Aktualisierung der Balance
Ausgleichen

Das Einfügen eines neuen Elementes erfolgt über die Methode insertNode (Programm 14.14), die im Gegensatz zu der Einfügeoperation des einfachen Suchbaumes rekursiv implementiert ist. Die rekursive Variante vereinfacht in diesem Fall das Ausgleichen des Baumes nach dem Einfügen, da die eventuell notwendigen Rotationen entlang des Pfades zur Wurzel ausgeführt werden müssen und der Pfad durch die rekursiven Aufrufe implizit verfügbar ist. In der Methode insertNode wird zunächst die richtige Position im Baum durch Vergleich mit dem aktuellen Knoten gesucht (1), wobei der aktuelle Knoten jeweils als Parameter n und das einzufügende Element als Parameter k übergeben werden. Wurde diese Position gefunden – im Fall des Einfügens im rechten Teilbaum ist dies daran erkennbar, dass der aktuelle Knoten n kein rechtes Kind besitzt –, wird ein neuer Knoten angelegt (5). Für den Knoten n wird außerdem die Balance aktualisiert: Wenn das neue Element als rechtes Kind eingefügt wurde, entspricht dies der Addition von 1, andernfalls muss der Wert 1 subtrahiert werden. Ist nun der Wert der Balance > 1 oder < − 1, so ist ein Ausgleichen notwendig, was über die globale Variable rebalance vermerkt wird. Abschließend liefert die Methode eine Referenz auf den aktuellen Knoten zurück.

Doppelrotation

Nach dem Einfügen in einen Teilbaum ist anhand der Variablen rebalance erkennbar, ob ein Ausgleichen notwendig ist (2). Allerdings ist der Pseudoknoten head dabei ausgenommen, da dieser ja immer auf die eigentliche Wurzel zeigen soll und somit nicht rotiert werden darf. Der Wert der Balance des aktuellen Knotens bestimmt die Art der Ausgleichsoperation. Für die Balance »1« muss die Balance des rechten Kindes konsultiert werden. Ist diese ebenfalls »1« so bedeutet dies, dass im rechten Teilbaum des rechten Kindes eingefügt wurde und somit eine einfache Rotation nach links durchgeführt werden muss. Andernfalls ist eine Doppelrotation notwendig, die in unserer Implementierung durch eine Rechts-Links-Rotation realisiert ist. Da beide Rotationen zu einer neuen Wurzel des Teilbaumes führen, wird diese in der Variablen tmp verwaltet und als Ergebnis der Methode zurückgegeben. Zuvor muss jedoch noch die Balance der neuen Wurzel auf »0« gesetzt werden. Da beim rekursiven Aufruf von insertNode das Ergebnis als rechtes bzw. linkes Kind des aktuellen Knotens eingetragen wird, kann die Änderung der Knotenreihenfolge auf diese Weise erfolgen. Die Fälle mit den Werten »0« und »-1« für die Balance des aktuellen Knotens erfordern keine Umordnung, da durch Einfügen eines Knotens im rechten Teilbaum dieser Wert im Bereich [−1 … 1] bleibt. Allerdings muss die Balance entsprechend aktualisiert werden, d.h., der Wert ist zu inkrementieren.

Programm 14.14 Einfügen im AVL-Baum

Im Programm 14.14 ist die Behandlung des »linken« Falls nicht dargestellt. Diese ist aber symmetrisch zum betrachteten Fall und kann leicht ergänzt werden.

Implementierung der Rotationen

Die Operationen zur Rotation sind ebenfalls als eigenständige Methoden implementiert (Programm 14.15), wobei nur die einfache Links- und die Rechts-Rotation benötigt werden, da die Doppelrotation durch Kombination dieser beiden Operationen realisiert werden kann. Die Rotationen selbst erfolgen durch »Umhängen« der Verweise auf die Kindknoten.

Programm 14.15 Rotationen im AVL-Baum

Löschen im AVL-Baum

Das Löschen im AVL-Baum erfordert im Prinzip das gleiche Vorgehen wie das Einfügen: Zunächst ist der entsprechende Knoten zu suchen, zu entfernen und schließlich die Balance des jeweiligen Teilbaumes durch Rotationen wiederherzustellen. Allerdings kann dieses Rotieren wiederum die Ausgeglichenheit des Elternknotens verletzen, so dass beim Löschen der gesamte Pfad aufwärts bis zur Wurzel verfolgt und für jeden Knoten gegebenenfalls die Balance wiederhergestellt werden muss. Dies kann wiederum rekursiv unter Verwendung der Rotationsmethoden aus Programm 14.15 implementiert werden, so dass wir an dieser Stelle auf die Darstellung der Java-Implementierung verzichten.

14.4.3B-Bäume

B-Baum

Eine weitere Variante einer ausgeglichenen Baumstruktur ist der von R. Bayer und E. McCreight entwickelte B-Baum. Hierbei steht der Name »B« für balanciert, breit, buschig oder auch Bayer, nicht jedoch für binär. Die Grundidee des B-Baumes ist es gerade, dass der Verzweigungsgrad variiert, während die Baumhöhe vollständig ausgeglichen ist.

Mehrwegebäume

Den Ausgangspunkt bildet somit auch wieder ein ausgeglichener Suchbaum, bei dem alle Pfade von der Wurzel zu den Blättern gleich lang sind. Eine Variation des Verzweigungsgrades bedeutet nun, dass ein Knoten mehrere Elemente enthalten kann – wir sprechen daher von Mehrwegebäumen.

Prinzip des B-Baumes

Wendet man das Kriterium der Ausgeglichenheit auf einen Mehrwegebaum an, so müssten folgende Forderungen für einen vollständig ausgeglichenen Baum erfüllt sein:

1. Alle Wege von der Wurzel bis zu den Blättern sind gleich lang.
2. Jeder Knoten besitzt gleich viele Einträge.

B-Baum-Kriterium

Das vollständige Ausgleichen in einem solchen Baum wäre jedoch zu aufwendig. Daher wird das B-Baum-Kriterium eingeführt:

Seiten
Einsatzgebiet

Im Kontext von B-Bäumen spricht man auch von Seiten anstelle von Knoten. Seiten entsprechen dabei Speichereinheiten, die auf einem externen Medium verwaltet werden und mit einer Operation ein- bzw. ausgelagert werden können. Daher sind B-Bäume besonders gut für Datenstrukturen geeignet, die aufgrund ihrer Größe nicht mehr im Hauptspeicher, sondern extern, d.h. beispielsweise auf der Festplatte oder einer CD-ROM, gespeichert werden. Da eine Seite (bzw. ein Knoten) mehrere Elemente umfassen kann, lassen sich mit einem Seitenzugriff mehrere Elemente vom externen Medium in den Hauptspeicher bewegen. So wird die Anzahl der Zugriffe auf den externen Speicher deutlich reduziert. Das wohl wichtigste Einsatzgebiet von B-Bäumen sind Datenbanksysteme. Hier werden B-Bäume als Indexstrukturen verwendet, die einen schnellen Zugriff auf die eigentlichen Datensätze über den Wert eines Elementes des Datensatzes (den sogenannten Schlüssel) ermöglichen.

Ordnung des B-Baumes

Der Aufbau einer Seite im B-Baum ist in Abbildung 14–24 dargestellt. Jede Seite enthält i geordnete Elemente oder Schlüsselwerte, wobei es einen Wert m gibt, so dass m ≤ i ≤ 2m gilt. Dieses m wird auch als Ordnung des B-Baumes bezeichnet. Zusätzlich zu den Schlüsselwerten enthält jede Seite noch Verweise auf die Kindknoten mit den Unterbäumen, wobei für einen inneren Knoten jeweils i + 1 solcher Verweise vorhanden sind.

Abb. 14–24 Struktur einer Seite im B-Baum

Höhe

Die Höhe eines B-Baumes ergibt sich danach bei minimaler Füllung aus log_m n. Gleichzeitig lassen sich somit n Datensätze mit log_m n Seitenzugriffen von der Wurzel zum Blatt lesen.

Verzweigungsgrad

Es sei noch angemerkt, dass in einigen Büchern als Ordnung auch der maximale Verzweigungsgrad bezeichnet wird. Dies entspricht hier also 2m + 1.

Mit diesen Begriffen können die Eigenschaften eines B-Baumes wie folgt definiert werden:

Definition 14.3 B-Baum

Für einen B-Baum der Ordnung m gilt:

1. Jede Seite enthält höchstens 2m Elemente.
2. Jede Seite außer der Wurzelseite enthält mindestens m Elemente.
3. Jede Seite ist entweder eine Blattseite ohne Nachfolger oder hat i + 1 Nachfolger, falls i die Anzahl ihrer Elemente ist.
4. Alle Blattseiten liegen auf der gleichen Stufe.

In Programm 14.16 ist eine mögliche Java-Definition der B-Baum-Knotenklasse Node sowie des B-Baumes selbst angegeben. Pro Knoten werden die Schlüssel (keys), die Verweise auf die Kindknoten (pointers), ein Verweis auf den Elternknoten (parent) sowie der Typ ntype des Knotens (Blatt = LEAF_PAGE bzw. innerer Knoten = NODE_PAGE) gespeichert. Der eigentliche Baum (Klasse BTree) benötigt dann nur noch den Wurzelknoten und die Ordnung (degree). Es ist zu beachten, dass die Knoten eines B-Baumes eigentlich auf den Externspeicher in Form von Seiten abgelegt bzw. von dort gelesen werden. Dieser Schritt ist in den folgenden Programmbeispielen zur Vereinfachung der Darstellung weggelassen. Ebenfalls nicht dargestellt sind einfache Zugriffsmethoden zum Auslesen der Felder (getKey(int idx) für die Schlüssel, getPointer(int idx) für die Verweise, getParent() für den Elternknoten sowie getNumKeys() für die Anzahl der Schlüssel).

Programm 14.16 Knotenklasse für BTree

In den folgenden Abschnitten werden wir die Operationen Suchen, Einfügen und Löschen im B-Baum vorstellen. Eine sinnvolle Implementierung dieser Operationen müsste die Verwaltung von Seiten auf dem externen Speicher berücksichtigen, beispielsweise in Dateien. Da dies jedoch über den Rahmen dieses Buches hinausgehen würde, verzichten wir auf die Angabe einer entsprechenden Implementierung.

Suchen in B-Bäumen

Sortierte Folge

Aufgrund der Struktur eines B-Baumes basiert das Suchen auf einer Kombination des Verfolgens von Verweisen wie im binären Suchbaum und der Suche in einer sortierten Folge. Beginnend auf der Wurzelseite wird der Eintrag ermittelt, der den gesuchten Schlüsselwert w überdeckt. Da die Elemente auf einer Seite sortiert abgespeichert sind, bedeutet dies, das erste Element zu finden, das größer oder gleich w ist. Im Fall der Gleichheit wurde das Element gefunden, andernfalls muss der Verweis vor diesem Element zur nächsten Seite verfolgt werden. Konnte kein Element größer w gefunden werden, so wird entsprechend der letzte Verweis der Seite verwendet. Erreicht man dagegen bei der Suche eine Blattseite, die den gesuchten Wert nicht enthält, dann existiert der entsprechende Eintrag nicht im Baum.

In Abbildung 14–25 ist dies am Beispiel der Suche nach dem Schlüsselwert 38 in einem B-Baum der Ordnung 2 dargestellt. Auf der Wurzelseite 0 wird durch Vergleich mit dem einzigen Element der Verweis auf Seite 2 ermittelt und verfolgt. Dort wird festgestellt, dass sich der gesuchte Schlüssel im Teilbaum zwischen den Elementen 31 und 40 befinden muss. Durch Verfolgen des entsprechenden Verweises zu Seite 7 und der Suche in der dortigen Folge der Schlüsselwerte kann das gesuchte Element schließlich gefunden werden.

Abb. 14–25 Suchen im B-Baum

Dieses Beispiel verdeutlicht auch, dass nur auf die drei Seiten 0, 2 und 7 zugegriffen werden muss, wobei dort jedoch jeweils eine lineare oder gegebenenfalls binäre Suche erfolgen muss. Da jedoch der Aufwand für das Laden einer Seite vom externen Speicher ungleich höher als der Vergleich von Schlüsselwerten im Hauptspeicher ist, bedeutet dies keinen Nachteil.

Betrachten wir hierzu die Implementierung in Programm 14.17 zur Knotenklasse aus Programm 14.16. Wir zerlegen das Problem der Suche in zwei Teilaufgaben: die Suche im Knoten (Methode findKeyInNode der Klasse BTree.Node) und darauf aufbauend die Suche im Baum (Methode find). Zum Schlüsselvergleich im Knoten wird die Methode compareTo aus der Schnittstelle java.lang.Comparable verwendet, wobei mehrere Fälle zu unterscheiden sind. Im Erfolgsfall (Schlüssel gefunden) wird der entsprechende Eintrag zurückgeliefert. Ist der Schlüssel im Knoten dagegen größer (res > 0), muss der Knotentyp berücksichtigt werden. Befinden wir uns auf einem Blattknoten, dann war die Suche erfolglos, im Fall eines inneren Knotens wird dagegen der Verweis auf den entsprechenden Kindknoten zurückgegeben. Die letzte Programmzeile behandelt dann nur noch den Fall, dass der gesuchte Schlüssel größer als der größte Schlüssel im Knoten ist. Somit liefert findKeyInNode folgende Ergebnisse:

• KEY_FOUND, wenn der Schlüssel im Knoten gefunden wurde; in diesem Fall wird der gefundene Schlüssel im Parameter keys geliefert,
• KEY_NOT_FOUND, wenn ein Blattknoten erreicht und der Schlüssel nicht gefunden wurde,
• einen Wert 0… keys.size()-1 im Fall eines inneren Knotens, wobei der Rückgabewert den Index des zu verfolgenden Verweises zum Kindknoten im Feld pointers repräsentiert.

Unter Verwendung dieser Methode kann die Suche im Baum implementiert werden. In Programm 14.16 wurde hierzu eine iterative Variante gewählt, alternativ könnte auch eine rekursive Lösung zum Einsatz kommen. Ausgehend vom Wurzelknoten wird der Schlüssel jeweils im aktuellen Knoten gesucht. Wird er gefunden oder nicht gefunden (es wurde ein Blatt erreicht), ist die Suche beendet. Andernfalls wird der Verweis verfolgt und die Suche im nächsten Kindknoten fortgesetzt.

Programm 14.17 Suchen im BTree

Einfügen und Löschen

Suchen der Blattseite

Bei den Einfüge- und Löschoperationen muss die Forderung nach mindestens m und maximal 2m Elementen pro Seite eingehalten werden. Für das Einfügen bedeutet dies konkret: Im ersten Schritt wird die Blattseite gesucht, der das einzufügende Element w zuzuordnen ist. Diese Seite hat entweder

• zwei Elemente v und x mit v ≤ w ≤ x,
• ein Element x als kleinstes Element der Seite mit w ≤ x und ist dabei die am weitesten links stehende Seite im Baum oder
• ein Element v als größtes Element der Seite mit v ≤ w und ist dabei die am weitesten rechts stehende Seite im Baum.

Einfügen in die Seite

Im zweiten Schritt wird das neue Element in die Seite eingefügt. Hierbei sind zwei Fälle zu unterscheiden:

• Die betroffene Seite hat n < 2m Elemente. In diesem Fall kann das Element w an der entsprechenden Stelle einsortiert werden.
• Die betroffene Seite hat bereits n = 2m Elemente. Daher muss in diesem Fall die Seitenstruktur des Baumes angepasst werden, indem eine neue Seite nach folgendem Schema erzeugt wird:
  1. Die ersten m Werte verbleiben auf der Originalseite.
  2. Die letzten m Werte werden auf die neue Seite verschoben.
  3. Das mittlere Element wandert in den Vaterknoten nach oben.

Hochwandern

Dieser Prozess muss eventuell rekursiv bis zur Wurzel wiederholt werden, falls durch das »Hochwandern« des mittleren Elementes in den Vaterknoten dort mehr als 2m Elemente vorhanden sind. Eine Besonderheit von B-Bäumen im Vergleich zu den bisher betrachteten Baumstrukturen ist daher auch, dass B-Bäume in Richtung der Wurzel wachsen.

Betrachten wir als ein Beispiel das Einfügen des Elementes 16 in den B-Baum aus Abbildung 14–25. Als passende Seite wird im ersten Schritt Seite 4 gefunden. Da diese Seite bereits vier Elemente enthält, müssen eine neue Seite erzeugt und die Elemente entsprechend aufgeteilt werden. Durch das Weiterreichen des mittleren Elementes (hier: 16) auf die Vaterseite ergibt sich die in Abbildung 14–26 dargestellte Struktur.

Der Aufbau eines B-Baumes unter Verwendung der Einfügeoperation ist in Abbildung 14–27 an einem einfachen Beispiel verdeutlicht. Der B-Baum hat die Ordnung m = 1. Dies bedeutet, dass mindestens ein und höchstens zwei Elemente in den Seiten enthalten sein können.

Abb. 14–26 Einfügen im B-Baum

Das Einfügen der Elemente 1 und 5 ist ohne Schwierigkeit möglich, da auf der Wurzelseite genug Platz ist. Mit dem Einfügen von 2 muss ein Überlauf behandelt werden: Die Seite wird geteilt (»Split«) und das mittlere Element 2 wird in die neue Wurzel verschoben. Während das nächste Element 6 auf einer existierenden Seite Platz findet, ist beim Einfügen von 7 wieder eine Überlaufbehandlung notwendig.

Nachdem die Elemente 4 und 8 ebenfalls auf noch freien Seiten eingefügt werden können, erfordert das Einfügen von 3 zunächst eine Teilung der Seite auf dem Niveau 1. Da dadurch aber die Wurzelseite »überläuft«, muss diese im nächsten Schritt ebenfalls geteilt werden, so dass sich schließlich der in der Abbildung 14–27 dargestellte B-Baum ergibt.

Die Implementierung dieser Operationen ist in Programm 14.18 dargestellt. Beginnen wir diesmal mit der insert-Methode der BTree-Klasse. Zunächst muss der passende Blattknoten für das Einfügen des Schlüssels gesucht werden (Methode findLeafNode). In diesen Knoten node wird nun mit der Methode insertIntoNode der neue Schlüssel eingefügt, wobei als Parameter noch eventuell vorhandene Kindknoten (lsibling und rsibling) mit übergeben werden. Im ersten Schritt sind diese aber leer und damit null. insertIntoNode liefert true, wenn das Einfügen einen Überlauf verursacht hat. In diesem Fall muss der mittlere Schlüssel des Knotens ermittelt und in der Variablen k gespeichert werden. Weiterhin wird der Elternknoten benötigt, da ja der Schlüssel k dort eingefügt werden muss. Betrifft der Split den Wurzelknoten, muss ein neuer Elternknoten und damit eine neue Wurzel angelegt werden. Schließlich wird der eigentliche Split durchgeführt und die Schleife durch das Einfügen des Schlüssels k und der beiden durch den Split entstandenen neuen Knoten in den Elternknoten fortgesetzt, bis kein weiterer Split notwendig ist.

Programm 14.18 Einfügen im BTree

Abb. 14–27 Aufbau eines B-Baumes

Die Methode findLeafNode ist ein einfaches Durchlaufen des B-Baumes von der Wurzel bis zu einem Blattknoten unter Verwendung der Suche im Knoten.

Auf Knotenebene werden noch eine Methode zum Einfügen (insertIntoNode) und eine Methode zum Split (split) benötigt (Programm 14.19). Beim Einfügen wird zunächst durch Schlüsselvergleich die Einfügeposition ermittelt. Existiert der Schlüssel bereits, wird die Operation abgebrochen – der neue Schlüssel wird einfach ignoriert. An der gefundenen Position i werden dann der Schlüssel obj und der rechte Kindknoten rnode – dieser jedoch an Position i+1 »rechts« vom Schlüssel – eingefügt. Wird der einzufügende Schlüssel das größte Element dieses Knotens, so wird er einfach angehüngt. Dieser Fall tritt auch auf, wenn der Knoten bisher leer war. Dann müssen sowohl der linke Kindknoten lnode als auch der rechte Kindknoten rnode eingefügt werden. Wird durch das Einfügen des Schlüssels ein Überlauf verursacht, d.h., ist die Anzahl der Schlüssel größer als die Ordnung multipliziert mit 2, wird der Wert true zurückgegeben. Beim Split wird zunächst ein neuer Geschwisterknoten erzeugt. Dann werden die obere Hälfte der Schlüssel und Verweise zum neuen Knoten kopiert und anschließend im alten Knoten gelöscht.

Programm 14.19 Einfügen und Split im BTree-Knoten

Unterlauf

Das Löschen im B-Baum erfolgt im Prinzip auf ähnliche Weise. Allerdings ist hier ein möglicher Unterlauf von Seiten zu berücksichtigen, der eintritt, wenn durch das Löschen des Elementes weniger als m Elemente auf der Seite verbleiben. Im Detail sind folgende Schritte auszuführen: Zunächst muss die Seite mit dem zu löschenden Element w gefunden werden. Im zweiten Schritt wird dann das Element entfernt, wobei zwei Fälle zu unterscheiden sind:

• Falls w auf einer Blattseite gespeichert ist, kann das Element gelöscht werden. Verbleiben danach weniger als m Elemente auf der Seite, ist ein Unterlauf zu behandeln.
• Wenn dagegen w auf einer inneren Seite gespeichert ist, so wird das Element gelöscht und durch das nächstkleinere Element von einer Blattseite ersetzt. Ergibt sich danach für diese Blattseite ein Unterlauf, so muss dieser wiederum behandelt werden.

Behandlung des Unterlaufs

In beiden Fällen kann die Behandlung des Unterlaufs entweder durch Ausgleichen oder durch das Vereinigen von zwei Seiten zu einer erfolgen. Das Ausgleichen kann angewendet werden, wenn die Nachbarseite n Elemente mit n > m besitzt. Dabei werden die Elemente der beiden beteiligten Seiten sowie das »eingeschlossene« Element der Vaterseite neu verteilt, so dass auf beiden Seiten n Elemente mit n ≥ m vorhanden sind. Entsprechend muss auch das mittlere Element neu gewählt werden.

Für den Baum in Abbildung 14–25 ergibt sich diese Situation z.B. beim Löschen des Elementes 22. Bei einer Ordnung 2 zieht das Entfernen dieses Elementes einen Unterlauf auf der Blattseite nach sich. Da die linke Nachbarseite voll besetzt ist, können die Elemente 13, 14, 17, 18, 20 und 24 neu verteilt werden, so dass 13, 14 und 17 auf der linken Seite verbleiben, die betroffene Seite die Elemente 20 und 24 enthält und das Element 18 in den Vaterknoten eingetragen wird. In Abbildung 14–28 ist das Ergebnis dieser Operation im linken Teilbaum dargestellt.

Zusammenlegen von Seiten

Falls die Nachbarseite jedoch nur n = m Elemente besitzt, werden Unterlaufseite und Nachbarseite zusammengelegt. Zusätzlich muss noch das von beiden Seiten »eingeschlossene« Element der Vaterseite heruntergezogen werden, da durch das Zusammenlegen einer der beiden Verweise überflüssig geworden ist. Die neue Blattseite hat demzufolge 2m Elemente: m − 1 Elemente der Unterlaufseite, m Elemente der Nachbarseite und ein Element der Vaterseite. Da die Vaterseite nun ein Element weniger enthält, muss eventuell wieder ein Unterlauf dieser Seite behandelt werden.

Abb. 14–28 Löschen im B-Baum I

Abb. 14–29 Löschen im B-Baum II

Das Zusammenlegen von Seiten ist beispielsweise in einer geringfügig modifizierten Variante des B-Baumes aus Abbildung 14–25 beim Löschen des Elementes 43 notwendig. Da die linke Nachbarseite der betroffenen Seite nur zwei Elemente besitzt, können beide Seiten vereinigt werden. Die Elemente dieser neuen Seite sind demnach 32, 38 und 42. Außerdem verliert die darüber liegende Seite das Element 40, welches ebenfalls in die neue Seite aufgenommen wird. Das Ergebnis ist in Abbildung 14–29 sichtbar. Ohne das dritte Element 50 in Seite 2 wäre hier die Unterlaufbehandlung auch für diese Seite notwendig.

Durch das »Herausziehen« des mittleren Elementes der Vaterseite schrumpfen B-Bäume somit auch an der Wurzel.

Die Implementierung dieser Operationen unter Nutzung der BTree-Klasse sei an dieser Stelle dem Leser überlassen.

Komplexität der Operationen

Größe einer Seite
Seitenzugriffe

Der Aufwand der Operationen Einfügen, Suchen und Löschen in einem B-Baum der Ordnung m beträgt immer O(log_m n). Da dies genau der »Höhe« des Baumes entspricht, sind B-Bäume insbesondere für sehr große Datenmengen und mit einer großen Anzahl von Elementen pro Seite praktikabel. So beträgt beispielsweise in Datenbanksystemen als ein typisches Anwendungsgebiet für B-Bäume die Größe einer Seite ca. 4 KByte. Nimmt man weiterhin als Größe für ein Element 32 Byte und für einen Verweis auf den Nachfolgeknoten 8 Byte an, so lassen sich zwischen 50 und 100 Einträge auf einer Seite unterbringen. Ein solcher Baum hat damit die Ordnung 50. Selbst bei einer Menge von 1.000.000 Datensätzen sind im schlechtesten Fall nur log₅₀ 1.000.000 = 4 Seitenzugriffe notwendig. Daran wird deutlich, dass mit dem B-Baum die Anzahl der Blöcke oder Seiten, die von der Festplatte in den Hauptspeicher transferiert werden müssen, optimiert wird.

14.5Digitale Bäume

Digitale Bäume

Bei den Suchbäumen in den bisher betrachteten Formen werden die Schlüssel in den Knoten selbst gespeichert. So können die Bäume z.B. durch Ausgleichen oder Anpassen des Verzweigungsgrades an die tatsächlichen Daten angepasst werden. Bei langen Schlüsselwerten wie beispielsweise Zeichenketten erfordert diese Art der Speicherung aber erstens viel Platz und zweitens muss bei jeder Vergleichsoperation ein vollständiger Schlüsselvergleich durchgeführt werden. Als eine Alternative wurden daher digitale Bäume als eine spezielle Form von Mehrwege-Suchbäumen entwickelt, die auf einer festen Verzweigung unabhängig von den gespeicherten Schlüsselwerten basieren. Die Bezeichnung »digital« leitet sich aus der Behandlung der Schlüssel ab: Diese werden als Ziffernfolgen eines Zahlensystems zur Basis M betrachtet. Digitale Bäume lassen sich so nur für Datentypen anwenden, bei denen eine derartige feste Verzweigung sinnvoll ist, d.h. im Wesentlichen für Zeichenketten über einem festen Alphabet. Hier kann das Verzweigen nach jeweils einem Buchstaben des Schlüssels erfolgen, wobei der Verzweigungsgrad gleich der Anzahl der möglichen Zeichen des Alphabets ist.

Zur Klasse der digitalen Bäume zählen eine Reihe von Verfahren, von denen wir im Folgenden Tries und Patricia-Bäume kurz vorstellen werden.

14.5.1Tries

Retrieval

Ein Trie (gesprochen wie das englische Wort »try«) ist eine Baumstruktur zur Speicherung von Zeichenketten, die das Suchen von Texten unterstützt. Die Hauptanwendung ist das Text Retrieval (daher auch der Name: Retrie val), wo große Bestände von Textdokumenten auf das Enthaltensein von bestimmten Zeichenketten durchsucht werden sollen. Zu diesen Dokumenten wird ein sogenannter Index auf Basis eines Tries aufgebaut, der alle enthaltenen Wörter umfasst. In der Praxis werden natürlich zuvor die für die Suche nutzlosen Füllworter »und«, »oder« etc. sowie Artikel u.Ä. entfernt. Werden zu jeder Zeichenkette im Trie noch die sie enthaltenden Dokumente gespeichert, so kann die Suche ausschließlich auf dem Trie erfolgen und somit deutlich effizienter durchgeführt werden.

Struktur eines Tries

Die Struktur eines Tries ist in Abbildung 14–30 dargestellt. Jeder Knoten entspricht einem Feld, dessen Größe gleich der Kardinalität des verwendeten Alphabets ist. Jedes Feldelement enthält einen Verweis auf einen anderen Knoten oder auf einen Datensatz. Für ein Alphabet, bestehend aus den Großbuchstaben ohne Umlaute, muss jeder Knoten demzufolge ein Feld mit 26 Verweisen besitzen. Da die Buchstaben und ihre Reihenfolge für jeden Knoten identisch sind, müssen sie selbst nicht mit in den Knoten abgespeichert werden.

Abb. 14–30 Struktur eines Knotens im Trie

Ein Beispiel für einen Trie auf diesem Alphabet ist in Abbildung 14–31 in Ausschnitten angegeben. Hier wird auch das Prinzip der Suche im Trie deutlich: Für jedes Zeichen des Suchschlüssels wird ausgehend von der Wurzel der jeweilige Verweis des aktuellen Knotens verfolgt, bis der Datensatz gefunden wird oder erfolglos abgebrochen werden muss.

Problem von Tries

Ein Problem von Tries wird bei einer ungleichmäßigen Verteilung der Daten deutlich. Gerade nichtvorhandene Buchstaben oder Buchstabenkombinationen in den Daten führen bei inneren Knoten zu leeren Verweisen. So gibt es beispielsweise nur wenige Namen, die mit X oder Y beginnen, und auch Kombinationen wie XX, XY, YYY u.Ä. kommen eher selten vor. Darüber hinaus sind aber durchaus längere Folgen von Zeichen mit jeweils nur einem Nachfolger möglich, die damit zur Liste entarten. Dadurch müssen unter Umständen unnötigerweise lange Folgen ohne Verzweigungen verfolgt werden.

Abb. 14–31 Beispiel eines Tries

Binäre Tries
Binärkodierung

Eine spezielle Form von Tries sind binäre Tries, die auf einem binären Alphabet aus den Zeichen { 0, 1} basieren. Die Daten werden somit als Bitfolgen interpretiert, d.h., die Verzweigung im Baum erfolgt in Abhängigkeit vom Wert der betrachteten Bitposition. Eine mögliche Implementierung eines solchen Tries wollen wir im Folgenden betrachten. Zur Vereinfachung nehmen wir an, dass nur Zeichen im Bereich ’a’ … ’z’ als Schlüssel verwendet werden und jeder Schlüssel auch nur einmal vorkommt. Die 26 möglichen Schlüsselwerte lassen sich somit als Bitfolgen aus nur 5 Bits kodieren, etwa auf Basis der Reihenfolge im Alphabet, d.h. ’a’ mit dem Binärwert 00001, ’b’ mit dem Wert 00010, ’c’ mit dem Wert 00011 usw.

Zur Realisierung eines Tries müssen wir zwei Arten von Knoten unterscheiden: Innere Knoten verfügen entsprechend den möglichen Werten 0 und 1 über maximal zwei Nachfolger, äußere Knoten (Blätter) speichern den jeweiligen Schlüsselwert (hier ein char-Wert) mit. Diese verschiedenen Knoten sind in der Implementierung in Programm 14.20 durch jeweils eigene Klassen realisiert. Zur Unterscheidung der Knotentypen wird dabei eine Methode isLeaf() eingeführt; der Zugriff auf die Kindknoten bzw. den Schlüsselwert ist über entsprechende Methoden (setChild und getChild bzw. getKey) möglich.

Programm 14.20 Knotenklassen für einen binären Trie

BitSet

Betrachten wir zunächst das Einfügen in einen Trie mithilfe der Methode insertKey (Programm 14.21) am Beispiel der Schlüssel ’a’, ’l’, ’g’ und ’o’ (Abbildung 14–32). In dieser Methode wird zuerst der Schlüsselwert in die korrespondierende Bitfolge übersetzt (Methode keyToBitSet). Zur Repräsentation der Bitfolgen wird die Java-Klasse java.util.BitSet verwendet, die Methoden zum Setzen (set) und Lesen (get) einzelner Bits anbietet. Das Einfügen in einen leeren Baum (root == null) wird als Sonderfall behandelt, indem einfach ein neuer innerer Knoten als Wurzel erzeugt und der Blattknoten mit dem einzufügenden Schlüssel als Kind in den entsprechenden Zweig eingehängt wird (Abbildung 14–32; Schritt 1).

In allen anderen Fällen wird entsprechend den Werten der Bitfolge (beginnend bei Position 0) der Trie von der Wurzel her durchlaufen. Wird dabei ein leerer Blattknoten erreicht (d.h. ein Verweis auf null bzw. in Abbildung 14–32 durch ⊥ gekennzeichnet), so kann der neue Blattknoten an dieser Stelle direkt eingefügt werden (Abbildung 14–32; Schritt 2). Im Programm wird hierfür beim Durchlaufen des Tries der jeweilige Elternknoten in der Variablen parent mitgeführt. Gelangt man dagegen auf ein Blatt, das bereits einen Schlüssel enthält, muss dieses durch einen inneren Knoten ersetzt werden, wobei der alte Blattknoten und der neue Blattknoten mit dem einzufügenden Schlüssel als Kinder angehängt werden. Hierbei ist jedoch zu berücksichtigen, dass sich die beiden Schlüsselwerte nicht notwendigerweise an der aktuellen Bitposition unterscheiden, selbst wenn wir annehmen, dass es keine doppelt vorkommenden Schlüsselwerte gibt. In Abbildung 14–32 tritt dieser Fall beim Einfügen von o auf. Daher müssen so lange innere Knoten eingefügt werden, bis die erste abweichende Bitposition gefunden ist. In der insertKey-Methode erfolgt dies mithilfe der Methode compareBitSets. Zum Abschluss werden schließlich der alte und der neue Blattknoten an den »untersten« inneren Knoten angehängt.

Abb. 14–32 Einfügen in einen binären Trie

Programm 14.21 Einfügemethoden für den binären Trie

Die Suche im Trie gestaltet sich dagegen deutlich einfacher. In der Methode lookupKey (Programm 14.22) wird zunächst wieder der Schlüsselwert in eine Bitfolge konvertiert. Danach wird ausgehend von der Wurzel der durch die Bitfolge bestimmte Pfad bis zu einem Blattknoten (bzw. einem »leeren« Blatt) verfolgt. Wie bereits beim Einfügen wird die jeweilige Bitposition durch die Variable pos adressiert, die in jedem Schleifendurchlauf inkrementiert wird. Ist schließlich der erreichte Blattknoten null, konnte der Schlüssel nicht gefunden werden. Wird dagegen ein Blattknoten mit Schlüsselwert erreicht, muss noch der verbleibende Schlüsselteil verglichen werden. Die Notwendigkeit für diesen Schritt wird deutlich, wenn man im Trie aus Abbildung 14–32 nach dem Wert ’d’ (binär 00101) sucht. Im Trie gelangt man damit zum Blatt mit dem Wert ’a’, der bezüglich der beiden relevanten Bits die gleiche Folge repräsentiert. In unserer Implementierung wird dieses Problem einfach durch Vergleich mit dem im Blatt gespeicherten Schlüsselwert gelöst.

Programm 14.22 Suchen im binären Trie

Eine Anwendung derartiger binärer Tries ist das dynamische Hashen, das in Abschnitt 15.3 vorgestellt wird.

14.5.2Patricia-Bäume

Patricia-Baum
Anzahl der zu überspringenden Bits

Ein Ansatz, um das Verfolgen von zu Listen entarteten Teilbäumen zu vermeiden, ist der Patricia-Baum. Der Name steht dabei für Practical Algorithm To Retrieve Information Coded in Alphanumeric. Die Grundidee ist, dass Teile der Zeichenketten, die für den Vergleich bzw. das Verzweigen irrelevant sind, übersprungen werden. Dies wird erreicht, indem jeder Knoten die Anzahl der zu überspringenden Bits bzw. Zeichen enthält. So lässt sich die Position in der Zeichenkette bestimmen, die für die Entscheidung über den weiter zu verfolgenden Pfad zu testen ist. Im ursprünglichen Vorschlag zu diesem Verfahren wurde ein binärer Baum mit Bitfolgen verwendet, es lässt sich jedoch auch ein Alphabet, wie im vorigen Abschnitt beschrieben, nutzen. So zeigt Abbildung 14–33 einen Patricia-Baum zur Speicherung der Zeichenketten »Oberkante«, »Objektiv«, »Objektmenge« und »Objektmethode«. Die Zahlen in den Knoten geben die Anzahl der zu überspringenden Zeichen an, die Buchstaben an den Kanten bezeichnen die jeweiligen Verweise.

Abb. 14–33 Patricia-Baum

Auswertung der Indexinformation

Bei der Suche nach einer Zeichenkette müssen die Indexinformationen der Knoten mit ausgewertet werden. Ist der Suchbegriff zum Beispiel »Objektmenge«, so besagt der Wert 2 im Wurzelknoten, dass das 3. Zeichen zu testen ist. Entsprechend muss der Pfad mit »j« verfolgt werden. Beim nächsten Knoten ist die Position 7 auszuwerten usw. bis schließlich ein Blatt und damit der Datensatz erreicht ist.

Komprimierte Darstellung

Aufgrund der Struktur des Patricia-Baumes ergibt sich gegenüber dem einfachen Trie eine deutlich komprimierte Darstellung. Auch der Suchaufwand kann speziell bei sehr langen und weniger häufigen Wörtern reduziert werden.

Eine Variante des Patricia-Baumes sind die sogenannten Präfixbäume, bei denen nicht nur der Index des zu testenden Zeichens, sondern auch der Wert des übersprungenen Teilwortes im Knoten abgespeichert werden.

14.6Praktische Nutzung von Bäumen

Sortieren

In diesem Abschnitt wollen wir einige ausgewählte Aspekte des praktischen Einsatzes von Baumstrukturen betrachten. Zunächst werden wir das Problem des Sortierens wieder aufgreifen und ein Verfahren vorstellen, das durch Verwendung eines speziellen Baumes effizient realisiert werden kann. Weiterhin werden wir den Ensatz von Suchbäumen zur Implementierung des Datentyps Set beschreiben.

14.6.1Sortieren mit Bäumen: HeapSort

Heap

Die Idee des binären Baumes findet sich auch in einer anderen Datenstruktur wieder, die als Heap oder Halde bezeichnet wird und die Basis für einen effizienten und eleganten Sortieralgorithmus bildet. Da für das Verständnis dieses Verfahrens Kenntnisse über binäre Bäume notwendig sind, behandeln wir es erst an dieser Stelle und nicht im Zusammenhang mit den anderen Sortierverfahren in Abschnitt 5.2.

Heap-Eigenschaften

Die Datenstruktur Heap bezeichnet einen binären Baum, der folgende Eigenschaften erfüllt:

• Der Baum ist vollständig, d.h., die Blattebene ist von links nach rechts gefüllt.
• Der Schlüssel eines jeden Knotens ist kleiner (oder gleich) als die Schlüssel seiner Kinder. Diese partielle Ordnung wird auch als Heap-Eigenschaft bezeichnet.

Prioritätswarteschlange

Heap-Strukturen sind damit insbesondere dann geeignet, wenn nicht unbedingt eine vollständig sortierte Reihenfolge der Elemente festgelegt, sondern nur jeweils das größte bzw. das kleinste Element ausgewählt werden soll, da sich dieses Element immer in der Wurzel befindet. Ein solcher Anwendungsfall ist eine Prioritätswarteschlange, wo z.B. immer das Element mit der höchsten Priorität entnommen wird, während neue Elemente eingefügt werden können.

In Abbildung 14–34 ist ein Heap in Form eines binären Baumes dargestellt. Es wird einerseits die Heap-Eigenschaft deutlich, andererseits ist aber auch zu sehen, dass es sich nicht um einen Suchbaum handelt, da das jeweils linke Element nicht kleiner als das rechte sein muss.

Heap als Feld

Man kann einen Heap aber auch einfach über ein Feld darstellen. Dabei wird die Wurzel an der Position 1 abgelegt, deren Kinder an den Positionen 2 und 3, die Knoten der nächsten Ebene auf die Positionen 4, 5, 6 und 7 usw. Nummeriert man die Knoten des Heaps in Levelorder, so werden die Kinder des i-ten Knotens auf den Positionen 2i (für das linke Kind) und 2i + 1 (für das rechte Kind) abgespeichert. Entsprechend ist der Elternknoten eines Knotens j an der Position ⌊j/2⌋ zu finden. Da es sich beim Heap um einen vollständigen Baum handelt, ergeben sich auch keine Lücken im Feld. In Abbildung 14–35 wird dieses Prinzip an einem Beispiel gezeigt. Die Darstellung des Heaps als Feld ist insofern praktisch, da auf diese Weise Folgen von Elementen sortiert werden können, ohne dass zusätzliche Datenstrukturen aufgebaut werden müssen. Die Verarbeitung kann somit an Ort und Stelle erfolgen.

Abb. 14–34 Heap-Struktur

Abb. 14–35 Darstellung eines

Wurzel
Durchsickern

Ein Merkmal des Heaps ist es, dass die Wurzel immer das kleinste Element enthält. Man könnte nun die Elemente in einer sortierten Reihenfolge auslesen, wenn jeweils das Wurzelelement aus dem Baum entnommen wird. Allerdings weist der Baum danach ein »Loch« auf, so dass die Heap-Eigenschaft verletzt ist und wieder hergestellt werden muss. Dies lässt sich erreichen, indem das letzte Element, d.h. das sich im Baum am weitesten rechts befindende Element, entfernt wird und ausgehend von der Wurzel im Baum »durchsickert«. Das Durchsickern bedeutet dabei, das Element so lange im Baum nach unten zu bewegen, bis die Heap-Eigenschaft wieder erfüllt ist.

Dieses Prinzip wird in Abbildung 14–36 verdeutlicht. Nach dem Entfernen des Elementes 1 befindet sich an dieser Stelle ein Loch. Das letzte Element im Baum (hier: 11) wird nun zunächst an diese Stelle bewegt. Nun wird es mit den Elementen der Nachfolger verglichen und – falls eines oder beide kleiner sind – in Richtung des kleineren Elementes nach unten bewegt, d.h. mit diesem Element vertauscht. Im Beispiel werden demzufolge die Elemente 2 und 11 getauscht, so dass die Wurzel das Element 2 enthält. Da Element 11 immer noch die Heap-Eigenschaft verletzt, ist eine weitere Vertauschung mit dem Element 8 notwendig.

Abb. 14–36 Entfernen der Wurzel im Heap

Für die Verwendung im Rahmen eines Sortieralgorithmus sollte dieses Prinzip möglichst ohne zusätzlichen Speicherplatzbedarf realisierbar sein. Nutzt man zur Darstellung des Heaps ein Feld, so lässt sich die Tatsache ausnutzen, dass beim Entfernen der Wurzel das jeweils letzte Element des Baumes an deren Stelle bewegt wird. In einem Feld kann dies über eine einfache Austauschoperation implementiert werden. Wird dies schrittweise für alle Elemente durchgeführt, so entstehen im Feld zwei Partitionen: der linke unsortierte Teil mit dem Heap und der rechte Teil mit den sortierten Elementen. Mit jedem Schritt vergrößert sich dabei der sortierte Teil bis schließlich das gesamte Feld sortiert vorliegt.

Für den vollständigen HeapSort-Algorithmus muss nur noch sichergestellt werden, dass das zu sortierende Feld vor dem Entnehmen des ersten Elementes einen Heap repräsentiert (Algorithmus 14.9).

Algorithmus 14.9 HeapSort

Der erste Schritt dieses Algorithmus überführt das Feld in einen Heap, wobei wiederum das Prinzip des »Durchsickerns« angewendet wird. Beginnend beim letzten Element wird das gesamte Feld durchwandert und für jedes Element wird ausgehend von der ersten Position versucht, dieses weiter im Baum nach unten zu bewegen. Dabei lässt sich zur Reduzierung des Aufwandes noch ausnutzen, dass die Blätter des Baumes keine Kinder haben können, die eventuell kleinere Elemente besitzen und deshalb nicht betrachtet werden müssen. Bezogen auf ein Feld mit n Elementen bedeutet dies, dass nur die ersten n/2 Elemente untersucht werden müssen.

Aufbau eines Heaps

In Abbildung 14–37 ist der Aufbau eines Heaps aus einem Feld sowohl in Baum- als auch in Felddarstellung verdeutlicht. Bei der Feldlänge 6 ist das erste zu behandelnde Element auf Position 3 (hier: Element 8) zu finden und muss – da die Heap-Eigenschaft verletzt ist – mit seinem Nachfolger getauscht werden. Das nächste Element 1 erfordert keine Aktionen. Im letzten Schritt wird schließlich noch Element 5 betrachtet, das zunächst mit dem Element 1 und dann noch mit Element 3 vertauscht wird.

Abb. 14–37 Aufbau eines Heaps

Wiederherstellung der Heap-Eigenschaft

Nachdem das Feld einen Heap repräsentiert, kann durch das schrittweise Entfernen der Wurzel und die Wiederherstellung der Heap-Eigenschaft die eigentliche Sortierung durchgeführt werden. Ausgehend vom Heap aus Abbildung 14–37 ist in Abbildung 14–38 diese Sortierung dargestellt, wobei das Wurzelelement 1 aus Schritt (4) in Abbildung 14–37 bereits entfernt und durch das letzte Element (hier: 8) ersetzt wurde. Dabei ist im Feld der sortierte Bereich hervorgehoben. Die absteigende Sortierung entsteht dadurch, dass es sich bei dem verwendeten Heap um einen MinHeap handelt, bei dem sich das kleinste Element in der Wurzel befindet. Bei einem MaxHeap mit dem größten Element in der Wurzel und der Eigenschaft, dass die Nachfolger immer kleiner sind, ergibt sich eine aufsteigende Sortierreihenfolge.

Implementierung

Zur Implementierung des Algorithmus in Java benötigen wir zwei Hilfsmethoden: die bereits bekannte Methode swap zum Vertauschen zweier Elemente eines Feldes und eine Methode percolate, die das »Durchsickern« eines Elementes in einem durch ein Feld repräsentierten Heap vornimmt. Die eigentliche Sortiermethode heapSort in Programm 14.23 ist dann nur noch eine direkte Umsetzung von Algorithmus 14.9. Wir lassen dabei als Feldelemente Objekte zu, die die Schnittstelle Comparable unterstützen, so dass die Vergleichsoperationen durch Aufruf der compareTo realisiert werden müssen.

Die Methode percolate wird mit drei Parametern aufgerufen, die das Feld, die Position idx des aktuellen Elementes und die Position last des letzten zu betrachtenden Elementes bezeichnen. Die Heap-Eigenschaft wird somit für den Bereich idx… last hergestellt. Weiterhin ist noch die Besonderheit der Feldindizierung von Java zu berücksichtigen: Da hier das erste Element auf der Position 0 abgelegt wird, funktioniert die Bestimmung der Nachfolgerknoten für dieses Element nicht, da sich hierfür die Positionen 2 · 0 = 0 und 2 · 0 + 1 = 1 ergeben. Demzufolge muss zunächst mit einem Index von idx + 1 gearbeitet werden, der beim eigentlichen Zugriff auf das Feld wieder korrigiert wird.

Programm 14.23 Implementierung von HeapSort

Abb. 14–38 Sortierung des Heaps

Aufwand

Der Aufwand des Sortierens mit HeapSort setzt sich im Wesentlichen aus zwei Bestandteilen zusammen:

Aufbau des Heaps

• Aufwand für den Aufbau des Heaps
  Dies berechnet sich aus dem Aufwand für das Durchsickern eines Elementes multipliziert mit der Anzahl der Elemente n. Da das Durchsickern entlang eines Pfades im Baum erfolgt, entspricht der Aufwand im ungünstigsten Fall der Höhe des Baumes, d.h. log₂ n. Insgesamt ergibt sich somit für diesen Schritt n/ 2 · log₂n.

Sortierung

• Aufwand für das Entfernen der Elemente aus dem Heap zur eigentlichen Sortierung
  Das Entfernen erfolgt für jedes Element des Feldes, wobei der Aufwand für das Wiederherstellen der Heap-Eigenschaft durch das Durchsickern wiederum jeweils log₂n beträgt. Demzufolge ist dieser Schritt mit einem Aufwand von n log₂n verbunden.

Für den gesamten HeapSort-Algorithmus beträgt der Aufwand somit 3n/2 log₂n bzw. in der O-Notation unter Weglassen des konstanten Faktors O(n log n). HeapSort arbeitet damit im durchschnittlichen Fall wie MergeSort und QuickSort, hat aber auch im schlechtesten Fall einen Aufwand von O(n log n), während beispielsweise Quick-Sort hier O(n²) benötigt.

14.6.2Sets mit binären Suchbäumen

Eine weitere praktische Anwendung von Bäumen ist die Implementierung von anderen Datentypen. Als ein Beispiel wollen wir den Datentyp »Set« aus Abschnitt 11.2.3 betrachten. Dieser Datentyp kann über die folgende Java-Schnittstelle definiert werden:

Test auf Enthaltensein

In einer Implementierung muss zur Gewährleistung der Mengeneigenschaft im Wesentlichen ein Test auf Enthaltensein durchgeführt werden. So ist etwa beim Hinzufügen eines Elementes in der Methode add zu prüfen, ob dieses Element bereits vorhanden ist. Auch bei der Vereinigung (unite) bzw. der Bestimmung der Schnittmenge (intersect) ist diese Prüfung notwendig. Da der Test auf Enthaltensein somit möglichst effizient implementiert sein sollte, ist die Verwendung eines binären Suchbaumes zur Aufnahme der Elemente eine sinnvolle Variante.

AVL-Baum

In Programm 14.24 ist die Implementierung der Klasse TreeSet auf Basis eines AVL-Baumes nach Abschnitt 14.4.2 dargestellt. Diese Klasse implementiert die Methoden der Schnittstelle Set unter Nutzung der Baummethoden.

Programm 14.24 Implementierung von Set auf Basis eines Baumes

Mengenoperationen

Während die Methoden add und contains direkt die entsprechenden Methoden von AVLTree nutzen, weisen die Methoden zur Implementierung der Mengenoperationen einige Besonderheiten auf. So wird in unite zunächst ein neues Set-Objekt angelegt, dem die Elemente des aktuellen Objektes sowie des als Parameter übergebenen Objektes hinzugefügt werden. Da die add-Methode (bzw. die insert-Methode von AVLTree) bereits das Einfügen von Duplikaten verhindert, wird auf diese Weise die Mengensemantik erfüllt. In ähnlicher Weise können auch die weiteren Mengenoperationen implementiert werden.

Iterator-Konzept
Warteschlange vs. Keller

Das Navigieren über alle Elemente der Mengen erfordert wieder einen geeigneten Mechanismus, der das Traversieren eines Baumes mit dem Iterator-Konzept aus Abschnitt 13.5 verbindet. Die Schwierigkeit ist dabei die Umsetzung des rekursiven Traversierens in eine iterative Variante in Form einer Klasse mit der Schnittstelle java.util.Iterator, die bei jedem Aufruf der Methode next den nächsten Knoten liefert. Dies kann realisiert werden, indem die bei der rekursiven Variante des Traversierens implizit vorhandene Aufrufreihenfolge der Knoten explizit verwaltet wird, wie dies für das Levelorder-Auslesen in Algorithmus 14.4 vorgestellt wurde. Soll eine andere Knotenreihenfolge wie z.B. Inorder erzielt werden, so muss anstelle der Warteschlange ein Keller als Datenstruktur verwendet werden. Das sich daraus ergebende Prinzip ist in Abbildung 14–39 verdeutlicht.

Abb. 14–39 Prinzip des Iterators für einen Suchbaum (Inorder-Durchlauf)

Zunächst wird der Pfad von der Wurzel zum am weitesten links liegenden Knoten mit dem kleinsten Element verfolgt. Dabei werden alle Knoten auf diesem Pfad auf dem Stack abgelegt (Abbildung 14–39(a)). Bei jedem Iterationsschritt wird nun der jeweils oberste Knoten vom Stack entfernt. Besitzt dieser Knoten einen rechten Nachfolger so wird darüber wieder der Pfad zum am weitesten links liegenden Knoten dieses Teilbaumes mit dem nächstgrößeren Element verfolgt (Abbildung 14–39(b)). Auch hier werden alle Zwischenknoten auf den Stack gespeichert und anschließend wie beschrieben weiterverarbeitet.

Die Umsetzung dieses Prinzips im Rahmen der Klasse TreeSetIterator ist in Programm 14.25 dargestellt. Der Iterator benötigt als Attribute eine Referenz auf den Suchbaum sowie ein Stack-Objekt für die Ablage der Knoten. Im Konstruktor wird der Stack soweit initialisiert, dass der kleinste Knoten als oberstes Element abgelegt wird.

Programm 14.25 Iterator für TreeSet

Die next-Methode implementiert das oben beschriebene Verfahren des Traversierens. Das »Ende« des Baumes ist erreicht, wenn alle Elemente verarbeitet wurden und somit der Stack leer ist. Dieser Sachverhalt wird in der Methode hasNext getestet.