Baum (Datenstruktur)
Ein Baum ist eine Datenstruktur, in der auch größere Datenmengen so abgelegt werden können, dass besonders schnell auf sie zugegriffen werden kann; schneller, als dies etwa bei einer verketteten Liste möglich wäre.
Bäume allgemein
Allgemein besteht ein Baum aus Knoten und Kanten. Diese Kanten haben eine Richtung und zeigen vom so genannten Vaterknoten zu seinem Kind. Es darf nie einen Kreis aus Kanten geben. Hat ein Knoten keine Kinder, wird er als Blatt bezeichnet. Ein Knoten ohne Vater heißt Wurzel. Eine Reihe von aneinanderhängenden Kanten mit derselben Richtung und Knoten heißt Weg. Die Anzahl der Kanten von der Wurzel zum tiefsten Blatt ist die Höhe des Baums.
Wenn man einen Baum grafisch darstellt, zeichnet man unintuitiverweise die Wurzel nach oben und die Blätter nach unten.
Mathematisch ist ein Baum nichts weiter als ein gerichteter kreisfreier zusammenhängender Graph.
Die folgende Abbildung zeigt beispielhaft einen Baum, der einige Staaten, Bundesländer und Städte Europas darstellt. Jede Kante entspricht dabei einer X liegt in Y-Beziehung: Kufstein gehört zu Tirol, Tirol gehört zu Österreich, Österreich gehört zu Europa. Allgemeiner gilt das auch für alle Wege: Kufstein liegt auch in Österreich und in Europa, Tirol liegt auch in Europa.
Anwendungen
Die Domains im Domain Name System sind ebenso in einer Baumstruktur organisiert wie die Elemente eines XML-Dokuments.
Binäre Bäume
Ein binärer Baum ist ein Baum, in dem jeder Knoten höchstens zwei Kinder haben darf.
Ein binärer Baum kann sehr effizient als Array gespeichert werden, weil sich für jeden Knoten die Indizes seiner Kinder leicht berechnen lassen:
Der Knoten hat dabei immer genau die Kinder und .
Ein binärer Baum kann auch rekursiv definiert werden. Ein Baum ist entweder leer oder besteht aus einem Wurzelelement, einem linken Teilbaum und einem rechten Teilbaum.
Suchbäume
Ein Suchbaum ist ein binärer Baum, der das Prinzip der binären Suche verkörpert. Ein Suchbaum erfüllt folgende Eigenschaft: alle rechten Kinder und Kindeskinder eines Knoten sind größer als dieser, alle linken Kinder und Kindeskinder sind kleiner.
Wenn man ein neues Element zu einem Suchbaum hinzufügen möchte, gibt es dafür immer exakt eine richtige Position. Falls man in den abgebildeten Baum zum Beispiel ein Element mit der Nummer 101 hinzufügen möchte, betrachtet man zunächst die Wurzel: 123. 101 ist kleiner als 123, also muss die 101 in den linken Teilbaum eingefügt werden. Dessen Wurzel ist 42 – 101 ist größer als 42, also muss die 101 in den rechten Teilbaum eingefügt werden. Dessen Wurzel ist 69, 101 ist größer als 69, also muss die 101 rechts an die 69 angehängt werden.
Vorteile gegenüber Listen
Im Hinblick auf die Operationen Suchen, Einfügen und Entfernen sind binäre Suchbäume in der Regel schneller als verkettete Listen. Bei einer verketteten Liste mit Elementen muss man für jede dieser Operationen im schlimmsten Fall die gesamte Liste linear vom Anfang bis zum Ende durchlaufen, damit bewegt sich die Laufzeit in der Größenordnung .
Wenn ein Suchbaum gut balanciert ist, d.h. wenn für jeden Knoten der rechte und linke Teilbaum ungefähr gleich hoch sind, können diese Operationen in ausgeführt werden, da die Höhe eines gut balancierten Baumes mit Elementen etwa beträgt.
Balance
Ein Baum heißt balanciert, wenn alle seine Blätter ungefähr auf derselben Ebene liegen, beziehungsweise präziser: wenn sich von jedem Knoten der rechte und linke Teilbaum in der Höhe höchstens um 1 unterscheiden. Das Gegenteil von einem balancierten Baum ist ein so genannter entarteter Baum, ein Baum, dessen Knoten im Extremfall nur rechte oder nur linke Kinder haben. Diese Bäume sind (siehe Abbildung) nicht von verketteten Listen zu unterscheiden und bieten darum keine Vorteile bezüglich der Effizienz. Es ist aber mit geschickten Rotationen möglich, die Knoten eines Baumes neu anzuordnen, sodass die Suchbaum-Eigenschaft erhalten bleibt, aber der Baum besser ausbalanciert ist.
Die Höhe eines balancierten Baumes mit Knoten lässt sich ungefähr mit abschätzen, die Höhe eines entarteten Baums mit Knoten beträgt im schlimmsten Fall .
Implementierung
In Java könnte man einen binären Suchbaum folgendermaßen implementieren:
public class Tree
{
private Comparable root; // Elemente müssen vergleichbar sein
private Tree left;
private Tree right;
/** Konstruktor für den leeren Baum */
public Tree() {
this.root = null;
this.left = null;
this.right = null;
}
/** Konstruktor für nichtleere Bäume mit Wurzel und Kindern */
public Tree(Comparable root, Tree left, Tree right) {
this.root = root;
this.left = left;
this.right = right;
}
/** Sucht ein Objekt und liefert true zurück,
* wenn es gefunden wird, sonst false.
*/
public boolean find(Comparable obj) {
if (this.root.compareTo(obj) == 0) {
return true;
} else if (this.root.compareTo(obj) > 0) {
return left != null && left.find(obj);
} else {
return right != null && right.find(obj);
}
}
/** Fügt ein neues Objekt ein */
public void insert(Comparable obj) {
if (this.root == null) {
this.root = obj;
}
if (this.root.compareTo(obj) > 0) {
if (this.left == null) {
this.left = new Tree(obj, null, null);
} else {
left.insert(obj);
}
} else {
if (this.right == null) {
this.right = new Tree(obj, null, null);
} else {
right.insert(obj);
}
}
}
}
Heaps
Ein Max-Heap, auf deutsch auch Halde oder Haufen genannt, ist ein Binärbaum mit der Eigenschaft, dass jeder Knoten größer ist als seine beiden Kinder.
Das Gegenteil ist ein Min-Heap, bei dem jeder Knoten kleiner ist als seine Kinder.
Die Stärke von Heaps ist, dass man sehr leicht das größte bzw. das kleinste Element extrahieren kann, das ist nämlich die Wurzel und der Zugriff auf die Wurzel ist in . Den Platz der Wurzel nimmt das größere ihrer Kinder ein, dessen Platz nimmt das größere seiner Kinder ein usw. Dieser Platztausch muss für den ganzen Weg von der Wurzel zu einem Blatt durchgeführt werden und benötigt eine Laufzeit von .
Auch das Einfügen neuer Elemente läuft in : man fügt das Element am Ende an und tauscht es dann nach oben, bis es größer als seine Kinder und kleiner als sein Vater ist. Gegebenenfalls muss dann für das andere Kind ebenfalls getauscht werden.
Anwendungen von Heaps
Heaps kommen zum Einsatz, um Vorrangwarteschlangen (Queues) zu implementieren. Eine Vorrangwarteschlange enthält, allgemein gesprochen, Aufgaben, die zu erledigen sind und denen eine Priorität zugewiesen ist, die die Reihenfolge vorgibt. Mit dieser Datenstruktur lässt sich zum Beispiel die Reihenfolge, in der die Knoten beim Dijkstra-Algorithmus besucht werden, effizient organisieren. Auch der Sortieralgorithmus Heapsort arbeitet mit Heaps.
