Bäume und binäre Suchbäume

Ein Baum (Tree) ist eine hierarchische Datenstruktur, die aus Knoten und Kanten besteht. Grundbegriffe:

• Wurzel (Root): Der oberste Knoten ohne Elternknoten.
• Innerer Knoten: Ein Knoten mit mindestens einem Kind.
• Blatt (Leaf): Ein Knoten ohne Kinder.
• Tiefe eines Knotens: Anzahl der Kanten von der Wurzel zum Knoten.
• Höhe des Baumes: Maximale Tiefe eines Blattes.
• Teilbaum (Subtree): Ein Knoten mitsamt allen seinen Nachkommen.

Ein binärer Baum ist ein Baum, bei dem jeder Knoten höchstens zwei Kinder hat: ein linkes Kind und ein rechtes Kind.

class BaumKnoten<T> {
    T daten;
    BaumKnoten<T> links;
    BaumKnoten<T> rechts;

    BaumKnoten(T daten) {
        this.daten = daten;
    }
}

Ein binärer Suchbaum (Binary Search Tree, BST) ist ein binärer Baum mit der Suchbaumeigenschaft:

• Für jeden Knoten mit Wert k gilt:
• Alle Werte im linken Teilbaum sind kleiner als k.
• Alle Werte im rechten Teilbaum sind größer als k.

Beispiel: Ein BST mit den Werten 5, 3, 7, 1, 4, 6, 8:

        5
       / \
      3   7
     / \ / \
    1  4 6  8

Die Suche nutzt die Suchbaumeigenschaft und arbeitet ähnlich wie die binäre Suche:

algorithmus suche(knoten, wert):
    wenn knoten == null:
        gib NICHT GEFUNDEN zurück
    wenn wert == knoten.daten:
        gib knoten zurück
    wenn wert < knoten.daten:
        gib suche(knoten.links, wert) zurück
    sonst:
        gib suche(knoten.rechts, wert) zurück

Laufzeit: O(h) mit h = Höhe des Baumes. Bei einem balancierten BST: O(log n). Im Worst Case (entarteter Baum = „Liste“): O(n).

algorithmus einfuegen(knoten, wert):
    wenn knoten == null:
        gib neuen Knoten(wert) zurück
    wenn wert < knoten.daten:
        knoten.links = einfuegen(knoten.links, wert)
    sonst wenn wert > knoten.daten:
        knoten.rechts = einfuegen(knoten.rechts, wert)
    gib knoten zurück

Neue Elemente werden immer als Blatt eingefügt. Die Laufzeit ist ebenfalls O(h).

Es gibt drei klassische Methoden, einen binären Baum rekursiv zu durchlaufen:

• Inorder (LWR): Linker Teilbaum → Wurzel → Rechter Teilbaum. Bei einem BST liefert Inorder die Elemente in aufsteigend sortierter Reihenfolge!
• Preorder (WLR): Wurzel → Linker Teilbaum → Rechter Teilbaum. Geeignet zum Kopieren eines Baumes.
• Postorder (LRW): Linker Teilbaum → Rechter Teilbaum → Wurzel. Geeignet zum Löschen eines Baumes (Kinder vor Eltern).

Beispiel für den Baum oben (5,3,7,1,4,6,8):

• Inorder: 1, 3, 4, 5, 6, 7, 8 (sortiert!)
• Preorder: 5, 3, 1, 4, 7, 6, 8
• Postorder: 1, 4, 3, 6, 8, 7, 5

algorithmus inorder(knoten):
    wenn knoten != null:
        inorder(knoten.links)
        ausgabe(knoten.daten)
        inorder(knoten.rechts)

algorithmus preorder(knoten):
    wenn knoten != null:
        ausgabe(knoten.daten)
        preorder(knoten.links)
        preorder(knoten.rechts)

algorithmus postorder(knoten):
    wenn knoten != null:
        postorder(knoten.links)
        postorder(knoten.rechts)
        ausgabe(knoten.daten)

Wenn Elemente in sortierter Reihenfolge eingefügt werden, entartet der BST zu einer linearen Liste. Die Höhe wird n und alle Operationen degenerieren zu O(n).

Balancierte Bäume (z. B. AVL-Baum, Rot-Schwarz-Baum) garantieren eine Höhe von O(log n) durch automatische Umstrukturierung (Rotationen) nach dem Einfügen oder Löschen.

Abitur-Tipp: Präge dir die drei Traversierungsarten und ihre Merkwörter ein: Inorder = LWR (Links, Wurzel, Rechts → sortiert), Preorder = WLR (Wurzel zuerst), Postorder = LRW (Wurzel zuletzt). Typische Aufgabe: Gegeben ein BST, gib die Inorder-Traversierung an. Oder: Füge Elemente in einen leeren BST ein und zeichne den resultierenden Baum. Beachte, dass die Einfügereihenfolge die Baumstruktur bestimmt!