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.

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.

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 $x$ hat dabei immer genau die Kinder $2x+1$ und $2x+2$.

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 binärer Suchbaum

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 $n$ 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 ${\mathcal {O}}(n)$.

Wenn ein Suchbaum gut balanciert ist, d.h. wenn für jeden Knoten sind der rechte und linke Teilbaum ungefähr gleich hoch sind, können diese Operationen in ${\mathcal {O}}(\log(n))$ ausgeführt werden, da die Höhe eines gut balancierten Baumes mit $n$ Elementen etwa $\log(n)$ beträgt.

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 ${\mathcal {O}}(1)$. 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 ${\mathcal {O}}(\log(n))$.

Auch das Einfügen neuer Elemente läuft in ${\mathcal {O}}(\log(n))$: 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 z.B. Aufgaben, die zu erledigen sind und denen eine Priorität zugewiesen ist, die die Reihenfolge vorgibt.

Weblinks

• "Binäre Suchbäume" auf inf-schule.de 🇩🇪
• Binäre Suchbäume visualisiert auf VisuAlgo.net 🇬🇧🇨🇳🇮🇩