Binärer Suchbaum: Prüfungsfragen zu Einfügen und Löschen

Ein binärer Suchbaum (Binary Search Tree, BST) ist eine Datenstruktur, die Daten auch beim Einfügen und Löschen sortiert hält und Suchen, Einfügen und Löschen in O(log n) Schritten erledigt, solange sie balanciert bleibt. In der Klausur zu Datenstrukturen ist es das Thema mit den meisten Zeichenaufgaben: „Fügen Sie diese Schlüssel ein, löschen Sie jenen, zeichnen Sie den Baum, geben Sie die Preorder-Reihenfolge an.“ In diesem Beitrag halte ich die Regeln kurz und lege das Gewicht auf von Hand gelöste Aufgaben. Jeder Baum und jedes Traversierungsergebnis wurde von Hand und durch Ausführen des unten stehenden Codes überprüft.

Die BST-Eigenschaft

Für jeden Knoten gilt: Alle Schlüssel im linken Teilbaum sind kleiner als der Schlüssel des Knotens, alle Schlüssel im rechten Teilbaum sind größer. Die Regel gilt für den gesamten Teilbaum, nicht nur für die direkten Kinder; dieser Unterschied begegnet Ihnen in Aufgabe 6 wieder. Der Baum, den ich im ganzen Beitrag verwende, entsteht durch Einfügen von 50, 30, 70, 20, 40, 60, 80 in dieser Reihenfolge:

        50
      /    \
    30      70
   /  \    /  \
  20  40  60  80

Was mit gleichen Schlüsseln geschieht, hängt von der Vorlesung ab (abgelehnt, nach rechts einsortiert oder gezählt). In diesem Beitrag werden gleiche Schlüssel nicht eingefügt; in der Klausur gilt die Regel Ihrer Lehrkraft.

Knoten, Einfügen und Suchen

Ein Knoten ist eine gewöhnliche Klasse; wenn Sie Klassen und Referenzen auffrischen möchten, hilft der Beitrag zu Klassen und Objekten in C#.

public class Node
{
    public int Key;
    public Node? Left, Right;
    public Node(int key) => Key = key;
}

public static class Bst
{
    public static Node Insert(Node? node, int key)
    {
        if (node == null) return new Node(key);
        if (key < node.Key) node.Left = Insert(node.Left, key);
        else if (key > node.Key) node.Right = Insert(node.Right, key);
        return node; // gleicher Schlüssel: wird nicht eingefügt
    }

    public static bool Search(Node? node, int key)
    {
        while (node != null)
        {
            if (key == node.Key) return true;
            node = key < node.Key ? node.Left : node.Right;
        }
        return false;
    }
}

Einfügen und Suchen beginnen an der Wurzel und gehen bei kleinerem Schlüssel nach links, bei größerem nach rechts. Ein neuer Schlüssel wird immer als Blatt angehängt; vorhandene Knoten wechseln ihren Platz nicht. Verwendung: Node? root = null; root = Bst.Insert(root, 50);.

Löschen: drei Fälle

1. Blattknoten: wird direkt entfernt.
2. Knoten mit einem Kind: Das Kind rückt an die Stelle des gelöschten Knotens.
3. Knoten mit zwei Kindern: Der Schlüssel wird durch den Inorder-Nachfolger (das Minimum des rechten Teilbaums) ersetzt, danach wird der Nachfolger aus dem rechten Teilbaum gelöscht. Der Nachfolger kann kein linkes Kind haben, deshalb fällt dieses zweite Löschen immer in Fall 1 oder 2.

// innerhalb der Klasse Bst
public static Node? Delete(Node? node, int key)
{
    if (node == null) return null;
    if (key < node.Key) node.Left = Delete(node.Left, key);
    else if (key > node.Key) node.Right = Delete(node.Right, key);
    else
    {
        if (node.Left == null) return node.Right;  // Blatt oder nur rechtes Kind
        if (node.Right == null) return node.Left;  // nur linkes Kind
        Node successor = node.Right;
        while (successor.Left != null) successor = successor.Left;
        node.Key = successor.Key;
        node.Right = Delete(node.Right, successor.Key);
    }
    return node;
}

Manche Vorlesungen verwenden statt des Nachfolgers den Inorder-Vorgänger (das Maximum des linken Teilbaums). Beides ergibt einen gültigen BST, aber unterschiedliche Bäume; nehmen Sie, was die Aufgabe verlangt, und nennen Sie Ihre Wahl in der Lösung, wenn nichts vorgegeben ist.

Traversierungen

// innerhalb der Klasse Bst
public static void Inorder(Node? node, List<int> output)
{
    if (node == null) return;
    Inorder(node.Left, output);
    output.Add(node.Key);        // für Preorder an den Anfang, für Postorder ans Ende verschieben
    Inorder(node.Right, output);
}

public static List<int> LevelOrder(Node? root)
{
    var result = new List<int>();
    if (root == null) return result;
    var queue = new Queue<Node>();
    queue.Enqueue(root);
    while (queue.Count > 0)
    {
        Node current = queue.Dequeue();
        result.Add(current.Key);
        if (current.Left != null) queue.Enqueue(current.Left);
        if (current.Right != null) queue.Enqueue(current.Right);
    }
    return result;
}

Ergebnisse für den obigen Baum:

Traversierung	Reihenfolge	Ergebnis
Inorder	links, Wurzel, rechts	20 30 40 50 60 70 80
Preorder	Wurzel, links, rechts	50 30 20 40 70 60 80
Postorder	links, rechts, Wurzel	20 40 30 60 80 70 50
Level-Order	Ebene für Ebene, von links nach rechts	50 30 70 20 40 60 80

Die Inorder-Traversierung eines BST ist immer sortiert; das ist die schnellste Kontrolle für einen in der Klausur gezeichneten Baum. Bei Preorder steht die Wurzel immer an erster, bei Postorder immer an letzter Stelle.

Höhe, Balance und der entartete Fall

Die Höhe ist die Zahl der Kanten auf dem Weg von der Wurzel zum tiefsten Blatt; ein Baum mit einem Knoten hat die Höhe 0, der leere Baum −1. Manche Vorlesungen zählen stattdessen Knoten, dann ist jeder Wert um eins größer; prüfen Sie die Definition.

// innerhalb der Klasse Bst
public static int Height(Node? node) =>
    node == null ? -1 : 1 + Math.Max(Height(node.Left), Height(node.Right));

Jede Operation folgt einem einzigen Pfad von der Wurzel nach unten, die Kosten sind also O(h). Bei n Knoten ist h mindestens ⌊log₂ n⌋ und höchstens n − 1. Kommen die Schlüssel sortiert an (Aufgabe 5), wird der Baum zur verketteten Liste, und aus dem erwarteten O(log n) wird O(n).

Operation	Average Case	Worst Case (entartet)
Suchen	O(log n)	O(n)
Einfügen	O(log n)	O(n)
Löschen	O(log n)	O(n)
Minimum / Maximum	O(log n)	O(n)
Traversierung (jede)	O(n)	O(n)
Speicher	O(n) Knoten; rekursiv O(h) Stack	O(n)

Falls Ihnen die Notation nicht geläufig ist, erklärt der Leitfaden zu Big O und Laufzeitkomplexität, wie diese Tabelle zu lesen ist.

Aufgabe 1: Einfügen, dann 30 löschen

Aufgabe: Fügen Sie 50, 30, 70, 20, 40, 60, 80 in dieser Reihenfolge in einen leeren BST ein. Löschen Sie anschließend 30 und zeichnen Sie den Baum (mit Inorder-Nachfolger).

Lösung: 50 wird Wurzel. 30 < 50 geht nach links, 70 > 50 nach rechts. 20: kleiner als 50, kleiner als 30, also links von 30. 40: kleiner als 50, größer als 30, also rechts von 30. 60 und 80 landen nach derselben Überlegung links und rechts von 70; das Ergebnis ist der Baum vom Anfang des Beitrags.

30 hat zwei Kinder. Der Nachfolger ist das Minimum des rechten Teilbaums; dieser besteht nur aus 40, der Nachfolger ist also 40. 40 wird an die Stelle von 30 geschrieben, das alte Blatt 40 entfernt:

        50
      /    \
    40      70
   /       /  \
  20      60  80

Kontrolle: Inorder 20 40 50 60 70 80, sortiert. Mit dem Vorgänger würde 20 die 30 ersetzen, und 40 bliebe als rechtes Kind erhalten.

Aufgabe 2: alle vier Traversierungen angeben

Aufgabe: Geben Sie Inorder-, Preorder-, Postorder- und Level-Order-Traversierung des Baums aus Aufgabe 1 vor dem Löschen an.

Lösung: Preorder Schritt für Schritt: Wurzel 50 notieren; weiter in den linken Teilbaum: 30, dessen linkes Kind 20, dessen rechtes Kind 40; danach der rechte Teilbaum: 70, 60, 80. Ergebnis 50 30 20 40 70 60 80. Bei Postorder wird jeder Knoten nach seinen beiden Teilbäumen notiert: 20 40 30, dann 60 80 70, zuletzt 50. Alle vier Ergebnisse stehen in der Tabelle oben.

Für den Baum nach dem Löschen gilt: Preorder 50 40 20 70 60 80, Postorder 20 40 60 80 70 50, Level-Order 50 40 70 20 60 80.

Aufgabe 3: die Wurzel löschen, Nachfolger mit Kind

Aufgabe: Fügen Sie in den ersten Baum 65 ein und löschen Sie danach die Wurzel 50.

Lösung: 65 > 50 nach rechts, 65 < 70 nach links, 65 > 60 nach rechts: 65 wird rechtes Kind von 60.

        50
      /    \
    30      70
   /  \    /  \
  20  40  60  80
            \
            65

Für den Nachfolger von 50 geht man im rechten Teilbaum immer nach links: 70, dann 60; 60 hat kein linkes Kind, der Nachfolger ist 60. In die Wurzel wird 60 geschrieben. Nun muss der alte Knoten 60 weg; er hat ein (rechtes) Kind, also Fall 2: 65 rückt an seine Stelle und wird linkes Kind von 70.

        60
      /    \
    30      70
   /  \    /  \
  20  40  65  80

Kontrolle: Inorder 20 30 40 60 65 70 80. Der häufigste Fehler bei dieser Aufgabe: die 65 vergessen und aus dem Baum verlieren.

Am selben Baum lassen sich auch die beiden anderen Fälle zeigen: 20 ist ein Blatt und wird einfach entfernt. Wird 60 gelöscht (im Baum vor dem Löschen von 50), wird das einzige Kind 65 zum linken Kind von 70.

Aufgabe 4: einen BST aus der Preorder-Folge rekonstruieren

Aufgabe: Zeichnen Sie den BST mit der Preorder-Traversierung 40, 20, 10, 30, 25, 60, 50, 70 und geben Sie die Postorder-Folge an.

Lösung: Das erste Element einer Preorder-Folge ist die Wurzel: 40. Vom Rest bilden die Schlüssel kleiner als 40 (20, 10, 30, 25) den linken Teilbaum, die größeren (60, 50, 70) den rechten. Dieselbe Regel wird rekursiv angewandt: Links ist 20 die Wurzel, der kleinere Schlüssel 10 geht nach links, die größeren 30 und 25 nach rechts; dort ist 30 die Wurzel und 25 ihr linkes Kind. Rechts ist 60 die Wurzel, 50 links, 70 rechts.

          40
        /    \
      20      60
     /  \    /  \
   10   30  50  70
        /
      25

Postorder: 10 25 30 20 50 70 60 40. Die Höhe beträgt 3. Praktische Abkürzung: Fügt man die Schlüssel in Preorder-Reihenfolge in einen leeren BST ein, entsteht derselbe Baum. Bei einem allgemeinen Binärbaum reicht eine einzelne Traversierung nicht, um den Baum festzulegen; beim BST reicht sie, weil die Inorder-Folge ohnehin bekannt ist (die sortierten Schlüssel).

Aufgabe 5: sortiertes Einfügen und entarteter Baum

Aufgabe: Welche Höhe hat der Baum, wenn 10, 20, 30, 40, 50 in dieser Reihenfolge in einen leeren BST eingefügt werden? Wie viele Vergleiche braucht die Suche nach 50? Und wenn dieselben Schlüssel als 30, 20, 40, 10, 50 eingefügt würden?

Lösung: Jeder neue Schlüssel ist größer als alle bisherigen und wandert immer nach rechts:

10
  \
   20
     \
      30
        \
         40
           \
            50

Die Höhe ist 4 (n − 1), und um 50 zu finden, wird mit 5 Knoten verglichen; die Struktur ist faktisch eine verkettete Liste. Bei der zweiten Reihenfolge wird 30 Wurzel, 20 und 40 ihre Kinder, 10 und 50 hängen darunter: Höhe 2 und 3 Vergleiche für 50 (30, 40, 50). Gleiche Schlüsselmenge, andere Einfügereihenfolge, anderer Baum. AVL- und Rot-Schwarz-Bäume lösen das Problem, indem sie nach jedem Einfügen mit Rotationen ausbalancieren.

Aufgabe 6: Ist dieser Baum ein BST?

Aufgabe: Ist der folgende Baum ein binärer Suchbaum?

        50
      /    \
    30      70
   /  \
  20  55

Lösung: Nein. Vergleicht man jeden Knoten nur mit seinen eigenen Kindern, fällt nichts auf: 20 < 30 < 55 und 30 < 50 < 70. Aber 55 liegt im linken Teilbaum von 50 und ist größer als 50; die Regel gilt für den gesamten Teilbaum. Schnelle Kontrolle: Die Inorder-Folge 20 30 55 50 70 ist nicht sortiert. Im Code reicht die korrekte Prüfung den erlaubten Wertebereich an jeden Knoten weiter:

// innerhalb der Klasse Bst; Aufruf: IsBst(root, long.MinValue, long.MaxValue)
public static bool IsBst(Node? node, long min, long max)
{
    if (node == null) return true;
    if (node.Key <= min || node.Key >= max) return false;
    return IsBst(node.Left, min, node.Key) && IsBst(node.Right, node.Key, max);
}

Aufgabe 7: Suchpfad und Schranken für die Höhe

Aufgabe: (a) Welche Knoten werden im Baum mit 8 Knoten aus Aufgabe 3 (vor dem Löschen von 50) bei der Suche nach 65 und nach 45 besucht? (b) Welche Höhe hat ein BST mit 7 Knoten mindestens und höchstens?

Lösung (a): Für 65: 50, 70, 60, 65 – vier Vergleiche, gefunden. Für 45: 50, 30, 40; 40 hat kein rechtes Kind, die Suche endet nach drei Vergleichen erfolglos. Die leere Position, an der eine erfolglose Suche endet, ist genau die Stelle, an der 45 beim Einfügen landen würde.

Lösung (b): Mindestens 2: Ein Baum der Höhe h fasst höchstens 2^(h+1) − 1 Knoten, für h = 2 sind das genau 7 (der Baum vom Anfang des Beitrags). Höchstens 6: Beim sortierten Einfügen hat jeder Knoten nur ein Kind, die Höhe ist n − 1.

Wann verwenden – und wann nicht?

Wählen Sie einen BST, wenn sich die Daten ändern und Sie zugleich geordneten Zugriff brauchen: Minimum und Maximum, alle Schlüssel in einem Bereich, den Nachfolger eines Schlüssels, eine sortierte Ausgabe. Lautet die einzige Frage „Ist dieser Schlüssel vorhanden?“, ist eine Hashtabelle (Dictionary, HashSet) mit O(1) im Mittel die bessere Wahl, sie kennt aber keine Ordnung. Ändern sich die Daten nie, liefert die binäre Suche auf einem sortierten Array dieselbe Suche in O(log n) mit weniger Speicher; was das einmalige Sortieren kostet, steht im Beitrag zu den Sortieralgorithmen.

Einen unbalancierten BST in produktivem Code selbst zu schreiben, ist selten richtig; kommt die Eingabe sortiert an, bricht die Leistung ein. In .NET basieren SortedSet<T> und SortedDictionary<TKey, TValue> auf einem balancierten binären Suchbaum und garantieren O(log n). Der Wert eines selbst geschriebenen BST liegt darin zu verstehen, wie diese Strukturen arbeiten, und genau das prüft die Klausur.

Häufige Fehler

1. Das Ergebnis der Rekursion nicht zuweisen. Wer Insert(node.Left, key); schreibt, ohne den Rückgabewert node.Left zuzuweisen, erzeugt den neuen Knoten, hängt ihn aber nie in den Baum. Symptom: keine Fehlermeldung, aber der Baum wächst nicht, und Inorder gibt nur die Wurzel aus.

if (key < node.Key) Insert(node.Left, key);             // FALSCH: der neue Knoten geht verloren
if (key < node.Key) node.Left = Insert(node.Left, key); // RICHTIG

2. Bei der BST-Prüfung nur die Kinder ansehen. Der Baum aus Aufgabe 6 besteht diese Prüfung, ist aber kein BST. Verwenden Sie IsBst mit Wertebereich oder prüfen Sie, ob die Inorder-Folge sortiert ist.

3. Im Fall mit zwei Kindern das Löschen des Nachfolgers vergessen. Wird der Schlüssel kopiert, der alte Nachfolgerknoten aber stehen gelassen, kommt derselbe Schlüssel zweimal im Baum vor; eine Wiederholung wie ... 40 40 ... in der Inorder-Folge ist das Anzeichen. Hat der Nachfolger ein rechtes Kind (Aufgabe 3), gehört das Umhängen dieses Kindes zu diesem Schritt.

4. Nachfolger und Vorgänger verwechseln. Der Nachfolger ist der am weitesten links liegende Knoten des rechten Teilbaums, der Vorgänger der am weitesten rechts liegende des linken Teilbaums. „Ein Schritt nach rechts, dann immer nach links“ lohnt sich als Merksatz.

Wenn Sie Zeichenaufgaben an den Altklausuren Ihrer eigenen Vorlesung üben möchten, beschreibt die Seite zur Prüfungsvorbereitung, wie ich dabei vorgehe.

Häufig gestellte Fragen

Was ist der Unterschied zwischen einem BST und einem Binärbaum?

Ein Binärbaum legt nur fest, dass jeder Knoten höchstens zwei Kinder hat; über die Anordnung der Schlüssel sagt er nichts. Der BST ergänzt die Ordnungsregel: Im linken Teilbaum stehen kleinere, im rechten größere Schlüssel.

Nachfolger oder Vorgänger beim Löschen eines Knotens mit zwei Kindern?

Beides ist korrekt und hinterlässt einen gültigen BST, die entstehenden Bäume unterscheiden sich aber. Verwenden Sie in der Klausur das Verfahren aus Ihrer Vorlesung; ist nichts vorgegeben, schreiben Sie dazu, was Sie gewählt haben.

Kann derselbe Schlüssel zweimal in einen BST eingefügt werden?

Das hängt von der Definition ab. Üblich sind das Ablehnen des Einfügens, das konsequente Einsortieren gleicher Schlüssel in den rechten Teilbaum oder ein Zähler im Knoten. Suchen und Löschen müssen derselben Regel folgen.

Was ist der Unterschied zwischen einem AVL-Baum und einem BST?

Ein AVL-Baum ist ein BST, der den Höhenunterschied zwischen linkem und rechtem Teilbaum jedes Knotens bei höchstens 1 hält. Er balanciert sich nach dem Einfügen und Löschen durch Rotationen selbst aus und garantiert deshalb auch im Worst Case O(log n).