zurück zur Liste

Bäume

AVL-Bäume

AVL-Bäume (Adelson-Velskii und Landis) sind eine Form von binären Suchbäumen, die das Entarten vermeiden und dabei den Aufwand beim Ausgleichen begrenzt halten.

AVL-Kriterium: Ein AVL-Baum ist ein ausgeglichener/balancierter Binärbaum, d.h. für jeden Knoten unterscheidet sich die Höhe (= Weg von der Wurzel bis zum Knoten) seiner beiden Nachfolger um höchstens 1.

Durch diese Bedingung eignen sich AVL-Bäume besonders zur Suche, da im worst case eine Laufzeit von O(log n) entsteht.
Bei jeder Einfüge- oder Löschoperation muss die AVL-Bedingung über eine oder zwei Rotationen wieder hergestellt werden.

Einfügen in einen AVL-Baum

Das grundsätzliche Vorgehen beim Einfügen eines Elements entspricht dem Algorithmus vom binären Suchbaum. Als Folge dieser Operation kann jedoch die AVL-Eigenschaft verletzt sein, was man durch Vertauschen von Knoten (Rotation bzw. Doppelrotation) wieder behebt.

Rotation
Wenn es nach dem Einfügen eines neuen Wertes einen Knoten k0 gibt, dessen linker Teilbaum a des linken Kindes k1 und k1 (bzw. dessen rechter Teilbaum des rechten Kindes und das rechte Kind) eine um zwei größere Höhe hat als der rechte Teilbaum c (bzw. der linke Teilbaum), dann wird k0 mit k1 vertauscht.

Doppelrotation
Wenn es nach dem Einfügen eines neuen Wertes einen Knoten k0 gibt, dessen rechter Teilbaum b des linken Kindes k1 und k1 (bzw. dessen linker Teilbaum des rechten Kindes und das rechte Kind) eine um zwei größere Höhe hat als der rechte Teilbaum d (bzw. der linke Teilbaum), dann wird zunächst k1 mit seinem rechten Kind k2 (bzw. linken Kind) vertauscht und dann k2 nach oben rotiert, so dass dieser Knoten nun die neue Wurzel dieses Teilbaums ist.

Löschen in einen AVL-Baum

Ein gelöschter Knoten wird durch den linkesten Knoten seines rechten Teilbaums ersetzt. Hat der Knoten keinen rechten Teilbaum, wird er durch sein linkes Kind ersetzt. Der Baum wird danach durch Rotation und Doppelrotation wieder ausgeglichen falls nötig.

B-Bäume

B-Bäume sind keine Binärbaume, sondern ausgeglichene Mehrwegbäume. D.h. sie sind Bäume, die in einem Knoten mehrere Elemente speichern können.
Ein B-Baum der Ordnung m kann m-1 Elemente in einem Knoten speichern und hat folgende Eigenschaften:
  1. Jeder Knoten hat höchstens m Kinder.
  2. Jeder Knoten mit Ausnahme der Wurzel und der Blattknoten hat mindestens m/2 Kinder.
  3. Die Wurzel hat mindestens 2 Kinder (oder ist ein Blattknoten).
  4. Alle Blattknoten sind auf der gleichen Ebene, und tragen keine weiteren Informationen
  5. Ein innerer Knoten mit k Kindern besitzt k-1 Schlüssel.
Beispiel:
Grafik entnommen aus Saake, Sattler: "Algorithmen & Datenstrukturen"
2-3-Bäume bzw. 2-4-Bäume sind B-Bäume der Ordnung 3 bzw. 4. Die 2 gibt die minimale Anzahl der Kinder pro Knoten an.

Suchen in einen B-Baum

Nehmen wir an, dass wir einen (2,3)-Baum haben und einen Eintrag mit dem Wert w suchen.
Ein Knoten mit drei Elementen enthält die Werte a, b und c, wobei a ≤ b ≤ c, und vier Verweise, wobei v1 auf alle Elemente e verweist, die kleiner a sind, v2 auf alle a ≤ e < b, v3 auf alle b ≤ e < c und v4 auf alle c ≤ e.
Man fängt also wie gewohnt in der Wurzel an, überprüft, ob es dort einen Wert gibt, der gleich w ist. Wenn nicht nimmt man den jeweiligen Veweis zum nächsten Knoten und fährt rekursiv fort. Wenn man in einem Blatt angekommen ist und der Wert bis jetzt nicht gefunden wurde, ist er nicht im Baum gespeichert.

Einfügen in einen B-Baum

Zunächst wird das Blatt gesucht, in das das Element eingetragen werden soll und wird (der Sortierung entsprechend) eingefügt.
Dann gibt es zwei Fälle:
  1. Die Anzahl der Einträge des Knotens ist immernoch < m
  2. Die Anzahl der Einträge ist ≥ m
Im ersten Fall freut man sich, dann ist man nämlich mit dem Einfügen fertig.
Im zweiten Fall nimmt man das mittlere Element ei in den Elternknoten, teilt den Knoten in zwei und verweist jeweils recht und links von ei auf die neuen Knoten. Wenn nun der Elternknoten mehr als m-1 Elemente speichert, fährt man rekursiv fort. Dies kann sich bis zur Wurzel hochziehen. Hat die Wurzel nun mehr als m-1 Elemente wird ei nicht in den Elternknoten (gibt ja keinen), sondern wird in einen neuen Knoten geschrieben, der jetzt die Wurzel ist. Der B-Baum wächst also nach oben.

Löschen in einen B-Baum

Zunächst wird der Knoten gesucht, in das das Element gespeichert ist und der Eintrag gelöscht.
Dann gibt es drei Fälle:
  1. Die Anzahl der Einträge des Knotens aus dem gelöscht wurde ist immernoch ≥ m/2
  2. Die Anzahl der Einträge des Knotens ist < m/2
  3. Die Anzahl der Einträge des Blattes ist < m/2
Im ersten Fall freut man sich, dann ist man nämlich mit dem Löschen fertig.
Im zweiten Fall wird das Element durch den nächstkleineren aus einem Blatt ersetzt. Wenn sich für das Blatt nun ein Unterlauf ergibt, wird wie im dritten Fall fortgefahren.
Im dritten Fall gibt es wiederum zwei Möglichkeiten:
  1. Ein Nachbarknoten hat mehr als m/2 Elemente
  2. Die Nachbarknoten haben nur m/2 Einträge
Im ersten Fall werden der Knoten, der Nachbarknoten und ei aus dem Elternknoten, von dem aus rechts und links die beiden Verweise zu den Knoten ausgehen, kurzzeitig zu einem Knoten zusammengefasst, wieder halbiert und ein neues ei, was in den Elternknoten geschrieben wird, festgelegt.
Im zweiten Fall wird der Knoten, der Nachbarknoten und ei aus dem Elternknoten zusammengelegt. Einer der Verweise vom Elternknoten fällt weg (ist ja nur noch ein Knoten). Der neue Knoten hat m Einträge: (m/2)-1 vom ursprünglichen Knoten + m/2 vom Nachbarknoten + 1 der Knoten aus dem Elternknoten ei.
Möglicherweise gibt es nun im Elternknoten einen Unterlauf. Dieser wird rekursiv behandelt.
Darf ein Knoten nicht nur m-1 Einträge speichern?

Rot-Schwarz-Bäume

Eigenschaften:
  1. Knoten sind rot oder schwarz.
  2. Die Wurzel ist schwarz.
  3. Externe Knoten sind schwarz.
  4. Die Kinder von roten Knoten sind schwarz. (Rotbedingung)
  5. Jeder Pfad von einem Knoten x zu einem externen Knoten besitzt die gleiche Anzahl schwarzer Knoten.
    Diese Anzahl (x nicht mitgezählt gezählt) heißt schwarze Höhe bh(x) eines Knotens.

Rot-Schwarz-Baum
Die Grafik ist ein Screenshot von Arsen Gogeshvilis Binärbaum-Applet
(2,3)-Baum
Grafik entnommen aus Saake, Sattler: "Algorithmen & Datenstrukturen"

Jeder Rot-Schwarz-Baum lässt sich durch einen (2,3)-Baum darstellen und umgekehrt.
Ein 1-Knoten lässt sich durch einen schwarzen Knoten ersetzen, ein 2-Knoten durch einen schwarzen Knoten mit einem roten Kind und ein 3-Knoten durch einen schwarzen Knoten mit zwei roten Kindern.
Suchen, einfügen und löschen funktionieren also nach dem gleichen Prinzip wie im (2,3)-Baum.

Digitalbäume

Die Grafiken zu Digitalbäumen wurden den Folien zur Vorlesung entnommen.
Es gibt verschiedene Möglichkeiten einen Digitalbaum darzustellen.

Digitalbaum
Binärer Digitalbaum

Patricia-Bäume

Patricia-Bäume (Practical Algorithm To Retrieve Information Coded In Alphanumeric) sind binäre Digitalbäume.
Das Prinzip ist sehr einfach:

Alle Schlüssel werden in den Blättern gespeichert. In den Knoten steht die Anzahl der Zeichen (Bits), die auf den Wegen zu den Blättern überspringen werden können.

Ein richtiger Patricia-Baum sieht so aus:

Der Schlüssel HEINZ ist z.B. folgendemaßen abgespeichert: 10010001000101100100110011101011010
Wegfindung: 100100010
0
0
1
011001
0
011001110
1
01
1
010 		9 Bits überspringen
links
links
rechts
6 Bits überspringen
links
9 Bits überspringen
rechts
2 Bits überspringen
rechts ⇒ bei HEINZ angekommen

Suffix-Bäume

In einem Suffuixbaum sind alle Suffixe eines Wortes gespeichert.

Beispiel: Mississippi

Anmerkungen

Digitalbaum allgemein: zeichenweiser Schlüsselvergleich entscheidet über Pfad im Baum.
Digitalbaum speziell (Radix tree): Schlüssel in inneren Knoten und Blättern, zeichenweiser Schlüsselvergleich, keine Schlüsselordnung.
Trie: Schlüssel nur in Blättern, geordnet nach Schlüsseln.
Patricia Trie (Compressed Trie), (manchmal Patricia Tree): Redundanz eliminiert: jeder innere Knoten hat mindestens zwei Nachfolger.
Suffix Trie: Trie, der alle Suffixe einer Zeichenkette enthält (eher unwichtig, kommt selten vor).
Suffixbaum (Suffix Tree): Patricia Trie, der alle Suffixe einer Zeichenkette enthält, also: jeder innere Knoten mit zwei Nachfolgern. (wichtig)
Suffix-Feld (Suffix Array): Felddarstellung eines Suffixbaums (nicht behandelt).

Links

Das Applet zu AVL- und Rot-Schwarz-Bäumen
AVL-Applet mit einzelnen Umsortierungsschritten (zum Mitverfolgen)
Merkblatt zu Binäre Suchbäume & AVL-Bäume von Augustin
Merkblatt zu Rot-Schwarz-Bäume von Augustin
Merkblatt zu 2-3-Bäume von Augustin
Merkblatt zu Digitalbäume von Augustin Patricia-Bäume