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.

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.

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 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);
            }
        }
    }
}

Weblinks

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