B-Bäume

1. Einführung: Der Begriff "Baum"

Listen sind zwar relativ flexible Datenstrukturen, aber stets linear (eindimensional). Oft verwendet man auch zwei- oder dreidimensionale Datenstrukturen (mehrdimensionale Felder, ......), aber auch diese sind nicht wirklich flexibel, denn Elemente existieren nur an den festgelegten Positionen (bei Feldern durch Indizies gekennzeichnet). Zeiger ermöglichen aber den Aufbau von Datenstrukturen, die vom Programmierer beliebig geformt werden können. Eine der wesentlichsten derartigen Strukturen ist der Baum.

Man kennt Bäume oder baumartige Strukturen aus dem Alltag, zum Beispiel Familienbäume, Tennisturnier-Tabellen oder baumartige Firmenhierachien. Aus der Mathematik und aus Programmieren kennen wir den Graphen. Graphen bestehen aus Knoten und Kanten, die die Knoten verbinden. Bäume sind spezielle Graphen.

Allgemeine Definition: Ein Baum ist ein kreisfreier zusammenhängender Graph. Ein Baum besteht aus einer nichtleeren Menge von Knoten und Verbindungskanten. Ein Knoten heißt Wurzel, alle anderen Knoten können genau über einen Weg (Pfad) erreicht werden. Kreisfrei bedeutet, dass kein Weg von einem Knoten über eine Schleife von Kanten wieder zu diesem Knoten zurückführt (ohne eine Kante doppelt zu benutzen). Zusammenhängend bedeutet, dass ein Weg von jedem Knoten zu jedem anderen Knoten existiert.

Die Tiefe eines Knotens ist die Anzahl der Kanten auf dem Pfad von diesem Knoten zur Wurzel. Da nur ein solcher Pfad existiert, ist die Tiefe eindeutig. Die Tiefe der Wurzel ist also 0. Die Tiefe eines Baumes ist das Maximum der Tiefen aller Knoten; sie wird auch Höhe des Baumes genannt. Die Menge aller Knoten mit gleicher Tiefe im Baum wird auch Ebene (level) genannt.

Bäume haben unter anderem folgende Eigenschaften:

Ein Baum mit n Knoten hat n-1 Kanten.

Ein binärer Baum (ein Baum, dessen Knoten höchstens zwei Nachfolger haben) mit m Zwischenknoten hat höchstens m+1 Endknoten

Die Tiefe eines binären Baums mit n Knoten ist mindestens [ld n].

Bäume werden natürlich dazu verwendet, um in ihren Knoten Informationen zu speichern. Die Struktur des Baumes erlaubt es, vielfältige, flexible Operationen auf die Knoten zu formulieren. Wie bereits bei der Betrachtung der Knoten erwähnt, macht man sich die Selbstähnlichkeit (mit Hilfe von Rekursionen) der Bäume bei der Programmierung zunutze.

Binäre Bäume

Ein sogenannter binärer Baum ist ein Baum, dessen Knoten höchstens zwei Nachfolger haben. Im folgenden geht es um sortierte Bäume, sogenannte Suchbäume. Die Sortierung wird durch folgende Festlegung erreicht:

· linke Nachfolger eines Knotens sind kleiner als der Knoten

· rechte Nachfolger eines Knoten sind größer als der Knoten

Ein Beispielbaum

Doppelte Zahlen sind verboten. Wie man sieht, ist die Sortierung also rekursiv definiert. Alle linken Nachfolger der Wurzel sind also stets kleiner als die Wurzel, egal in welcher Tiefe sie liegen. Auch alle rechten Nachfolger eines linken Nachfolgers eines Knotens sind stets kleiner als der Knoten. Die Datenstruktur eines binären Baums bietet nichts besonderes: Sie ähnelt der Datenstruktur einer linearen Liste, nur enthält sie statt eines Zeigers auf den Nachfolger zwei Zeiger, einen auf den linken und einen auf den rechten Nachfolger.

Suchen

Die Formulierung des Sortierkriteriums ist eigentlich auch schon der Algorithmus zur Suche in einem binären Baum. Jeder Knoten ist zusammen mit seinen Nachfolgern ein vollständiger (Teil-)Baum. Daher kann man die Suche rekursiv definieren. Gesucht wird nach der Zahl x im Baum der oberen Abbildung.

info = 12 Datensatz gefunden, fertig.

info < 12 Im linken Teilbaum weitersuchen.

info> 12 Im rechten Teilbaum weitersuchen

Die gesuchte Zahl ist kleiner 12 und der Baum hat sie Struktur aus der oberen Abbildung. Nun wendet man den Vorgang auf den linken Nachfolger (6) von (12) an. Damit ist man dem Ziel (Finden des Knotens) ein Stück näher, oder schon fertig.

Beispiel: Die Funktion Suchen hat als Parameter die gesuchte Zahl x und einen Zeiger baum auf einen Knoten, der als Wurzel des zu betrachtenden Teilbaums angesehen wird. Die Funktion ruft sich solange selbst mit dem entsprechenden Nachfolger auf, bis entweder der gesuchte Knoten gefunden wurde oder aber baum gleich NIL ist, in diesem Fall war die Suche erfolglos. Zurückgegeben wird ein Zeiger auf den gefundenen Knoten oder NIL, wenn die Information noch nicht im Baum eingetragen ist.

Einfügen:

Auch das Einfügen ist rekursiv sehr kurz zu realisieren und ähnelt dem Suchen. Eingetragen werden kann in einem Baum nur an einem Nachfolger eines Endknotens. Da der Baum außerdem sortiert ist, kommt nur eine einzige Stelle in Frage, die rekursiv gefunden werden kann.

Wenn der Zeiger auf dem Teilbaum, in dem eingetragen werden soll, NIL ist, so hat man die Stelle gefunden und erzeugt einen neuen Teilbaum mit einem einzigen Knoten, der mit der übergebenen Information initialisiert wird. Wenn der Zeiger ungleich NIL ist, so vergleicht man den Schlüssel des Knotens mit der neuen Information und ruft mit dem rechten oder linken Teilbaum rekursiv auf. Voraussetzung für das Funktionieren dieser Routine ist, dass die Information noch nicht im Baum abgelegt ist (das kann durch Suchen vor dem Aufruf von Einfügen-Routinen leicht überprüft werden).

2.3 Löschen

Um einen binären Baum zu verwalten, fehlt noch das Löschen. Beim Löschen muss natürlich auch die geordnete Struktur erhalten bleiben. Einfach ist das Löschen in folgenden Fällen:

· Wenn der zu löschende Knoten ein Blatt ist, so muss man lediglich den Zeiger auf den Knoten gleich NIL setzen.

· Wenn es sich bei dem zu löschenden Knoten um einen Zwischenknoten mit nur einem Nachfolger handelt, so setzt man den Zeiger des Vorgängers auf den einen Nachfolger. Dabei ist egal, ob das ein linker oder rechter Nachfolger war.

· Wenn der zu löschende Knoten zwei Nachfolger hat, so muss die freiwerdende Stelle wieder so besetzt werden, dass die Sortierung erhalten bleibt. Man sucht nun unter den Nachfolgern des gelöschten Knotens einen, der die freigewordene Stelle gültig ausfüllen kann und der mit geringem Aufwand aus einer alten Position entfernt werden kann. Dieser Knoten wird dann an die freigewordene Stelle verschoben.

Natürlich darf man nur einen Knoten aus dem Baum an eine andere Stelle verlegen, weil ja sonst der Informationsgehalt des Baumes geändert werden würde. Es gibt zwei gleichwertige Möglichkeiten, aus welchen man den Ersatzknoten wählen kann:

der größte Datensatz im linken Unterteilbaum;

der kleinste Datensatz im rechten Unterteilbaum.

Abarbeiten eines binären Baums:

Ein Baum hat keine lineare Struktur wie etwa ein Feld oder eine Liste. Will man eine Operation auf alle Knoten eines binären Baumes anwenden, so muss man sich eine Reihenfolge überlegen. Selbstverständlich gibt es die Möglichkeit, die gewählte Strategie rekursiv zu definieren. Drei rekursive und eine nicht rekursive systematische Möglichkeit werden im folgenden besprochen; zum besseren Verständnis wird jeweils die Reihenfolge der Abarbeitung des Baums aus der oben gezeigten Abbildung. Die Implementierung der drei rekursiven Strategien unterscheiden sich nur in der Reihenfolge der rekursiven Aufrufe.

Preorder

Für jeden Teilbaum wir folgende Reihenfolge eingehalten:

Wurzel

Linker Teilbaum

Rechter Teilbaum

Es wird also zuerst die Wurzel bearbeitet, dann die Teilbäume. Der Ausdruck Preorder rührt daher, dass die Wurzel vor ("pre") den Teilbäümen abgearbeitet wird.

Abarbeitung des Bespielbaumes: 12-6-5-2-1-4-3-8-7-10-11-20-15-18-16-17-25-22-26

Inorder

Für jeden Teilbaum wird folgende Reihenfolge eingehalten:

Linker Teilbaum

Wurzel

Rechter Teilbaum

Die Wurzel wird also zwischen den beiden Teilbäumen bearbeitet.

Abarbeitung des Beispielbaums: 1-2-3-4-5-6-7-8-10-11-12-15-16-17-18-20-22-25-26

Wie man sieht, entspricht Inorder bei Suchbäumen der Abarbeitung in sortierter Reihenfolge.

Postorder

Für jeden Teilbaum wird folgende Reihenfolge eingehalten:

Linker Teilbaum

Rechter Teilbaum

Wurzel

Zuerst werden die Teilbäume bearbeitet und dann die Wurzel. Daher nennt man diese Strategie Postorder ("post" = danach)

Abarbeitung des Beispielbaums: 1-3-4-2-5-7-11-10-8-6-17-16-18-15-22-26-25-20-12

Levelorder

Hier wird der Baum in der folgenden Reihenfolge abgearbeitet:

Wurzel (Level 0)

Level 1

Level 2

Level 3

........

Zuerst wird die Wurzel bearbeitet, dann die unmittelbaren Nachfolger, dann deren Nachfolger etc.

Abarbeitung des Beispielbaums: 12-6-20-5-8-15-25-2-7-10-18-22-26-1-4-11-16-3-17

Hier wird der Baum Ebene für Ebene von der Wurzel aus abgearbeitet. Diese Methode ist nicht rekursiv zu implementieren. Eine mögliche Strategie zur Abarbeitung ist das Ablegen der Knoten in einer Queue.

Nachteile des binären Baums

Wenn der Baum nicht optimal ausgewogen ist, kann es das Suchen nach einem bestimmten Knoten sehr lange dauern. Eine gute Möglichkeit dieses Problem auszumerzen ist es, einen AVL-Baum zu benutzen. Dieser sollte immer möglichst ausgeglichen sein, und verkürzt somit die Suchzeit.

Normalerweise kann ein Binärer Baum nicht mehrere Knoten mit dem selben Schlüssel beinhalten, da dieser bei Bäumen ja eindeutig sein sollte. Dieses Problem kann man wiederum mit Hash-Tabellen gut lösen.

Das Löschen eines Knotens ist sehr kompliziert und geht in anderen Datenstrukturen um einiges leichter.

1353 Worte in "deutsch"  als "hilfreich"  bewertet