3.3 Binäre Suchbäume

In vielen Fällen wollen wir nicht nur am Anfang oder Ende unserer Datenstruktur etwas schreiben, sondern an beliebigen Stellen. Ganz allgemein wünschen wir uns eine Datenstruktur, die folgende Operationen unterstützt: 

find <key>           // findet das Paar (key,value) und gibt value zurück (oder null, wenn nicht vorhanden)
insert <key> <value> // fügt das Paar (key,value) ein und löscht ein etwaiges älteres Paar (key, oldValue) 
delete <key>         // löscht das Paar (key,value), sofern vorhanden

Wir wollen also Key-Value-Paare speichern, ähnlich wie in der Liste german-words.txt. Eine solche Datenstruktur nennt man im Allgemeinen ein Dictionary. Die meisten Programmiersprachen bieten Dictionarys bereits in der ein oder anderen Form an. Hier setzen wir uns mit den Möglichkeiten auseinander, ein solches zu implementieren und untersuchen jeweils, wie schnell (oder langsam) die jeweiligen Operationen sind.

  1. Als Stack, also z.B. verkettete Liste.
    • find <key>: wir müssen, wenn wir Pech haben, die ganze Liste durchlaufen; O(n).
    • insert <key> <value>: wir legen das Paar einfach auf den Stack drauf; das braucht O(1) Zeit; wenn wir allerdings vermeiden wollen, dass es mehrere Einträge mit dem gleichen Key gibt, dann müssen wir die ganze Liste durchlaufen: O(n).
    • delete <key>: gleich wie find
  2. Als Array, das immer nach den Werten der Schlüssel sortiert ist (z.B. alphabetisch, aufsteigend).
    • find <key>: Wir wenden binäre Suche an: O(log⁡n).
    • insert <key> <value>: Wir können den Einfügeort mittels binärer Suche schnell finden, müssen dann aber alles, was danach kommt, um eins nach rechts verschieben: O(n).
    • delete <key>: gleiches wie find; wir können zwar mittels binärer Suche die Stelle finden, müssen aber alles, was rechts davon steht, um eins nach links verschieben.

Um alle drei Operationen insert, find, delete in schneller (hier: O(log⁡n)) Laufzeit zu implementieren, brauchen wir eine neue Datenstruktur. Als erstes stellen wir den Binärbaum vor. Ein Binärbaum ist eine rekursive Datenstruktur, die entweder

  • ein leerer Baum ist, bestehend aus einem Blatt, oder
  • ein innerer Knoten mit einem Datenelement (beispielsweies einem String) und einem linken Kind und einem rechten Kind, die wiederum Binärbäume sind.

Den obersten Knoten nennen wir die Wurzel. Es ist recht problemlos, Binärbäume als Datentypen in Java oder Elm zu definieren. 

public class BST {
    public String data;
    public BST leftChild;
    public BST rightChild;
    public BST (String data, BST left, BST right) {
        this.data = data;
        leftChild = left;
        rightChild = right; 
    }
}
module BST exposing (..)


type BST
    = Leaf
    | Node String BST BST

Den folgenden Baum:

können wir dann wie folgt erzeugen:

// in Java
BST tree = new BST("z", new BST("e", null, new BST ("a", null, null)), null);
-- in Elm                                    
tree: BST 
tree = Node "z" (Node "e" Leaf (Node "a" Leaf Leaf)) Leaf

Binäre Suchbäume (Binary Search Trees, BST)

Ein Binärbaum ist ein Binärer Suchbaum (Abkürzung BST), wenn die in den inneren Knoten gespeicherten Elemente geordnet sind; konkret: wenn ein innerer Knoten das Element hat, dann sind alle Elemente im linken Teilbaum kleiner als und alle Elemente im rechten Teilbaum größer als . Wir sprechen nun auch nicht mehr von Elementen, sondern von Schlüsseln / Keys. Hier sehen Sie ein Beispiel, in welchem nacheinander Schlüssel in einen anfangs leeren BST eingefügt werden:
Klicken Sie auf das folgende Bild, um zu meiner interaktiven BST-App zu gelangen. Hier können Sie mit insert, find, delete experimentieren.
Demo für binäre Suchbäume
 Hier finden Sie meine Java-Implementierung für binäre Suchbäume: BT.java

Im folgenden werden wir BSTs formal definieren und Methoden zum Suchen, Einfügen und Löschen finden.

Definition 3.3.1

Ein binärer Suchbaum, kurz BST (vom Englischen binary search tree) ist wie folgt rekursiv definiert: es ist entweder ein leerer Baum, den wir mit bezeichnen, oder er ist nichtleer und von der Form

wobei in diesem Falle
  • wir als den Key des Wurzelknotens bezeichnen,
  • und wiederum BSTs sind,
  • alle Keys in kleiner als sind,
  • alle Keys in größer als sind.

Beachten Sie, dass wir im obigen Beispiel mit of, to, in... die leeren BSTs nicht gezeichnet haben. Mit den leeren BSTs müsste das Endergebnis des oberen Baums dann so aussehen:

Der (Pseudo-) Code für Suchen (find) und Einfügen (insert) in einem BST schreibt sich fast von selbst:

Der Code für das Einfügen ist nur leicht komplizierter:

Löschen ist etwas schwieriger. Ich teile es auf in delete, was erst einmal den Key überhaupt sucht und dann deleteRoot aufruft, was den Wurzelknoten mitsamt Key löscht.

Für delRoot müssen wir uns was überlegen. Einfach ist es, wenn der linke Teilbaum leer ist; dann ergibt delRoot(T) einfach den rechten Teilbaum. Ganz analog, wenn der rechte Teilbaum leer ist:

Wenn aber weder der linke noch der rechte Teilbaum leer ist, was dann? Eine Idee wäre, im rechten Teilbaum das kleinste Element zu finden; dieses sitzt in einem Blatt von , und zwar ganz links; dann schreiben wir dieses Element in den Wurzelknoten und löschen das entsprechende Blatt von .

Ich hatte fehlerhaft angenommen, dass das Minimum von in einem Blatt wohnt. Das muss nicht der Fall sein. Wie also können wir es löschen? Brauchen wir hierfür Rekursion oder geht es einfacher?

Übungsaufgabe 3.3.1 Schreiben Sie Pseudo-Code für findMin und deleteMin.
Übungsaufgabe 3.3.2 Machen Sie in dem obigen Beispiel weiter und fügen Sie he, by, or, on, do, if, me ein.
Übungsaufgabe 3.3.3 Nehmen Sie den obigen Suchbaum und löschen Sie of.

Ganz allgemein finden wir BSTs gut, wenn Sie geringe Höhe haben. Die Höhe eines Baumes ist der Abstand von der Wurzel zu dem am weitesten entfernten Blatt. Wir schreiben . Für ein Array schreiben wir für den BST, der entsteht, wenn wir die Elemente des Arrays in dieser Reihenfolge einfügen. Zum Beispiel:

und damit und .

Übungsaufgabe 3.3.4 Stellen Sie sich vor, Sie fügen die Elemente in einen anfangs leeren BST ein. Nennen wir diesen Baum . Jetzt fügen Sie ein weiteres Element ein. Offensichtlich kann die Höhe des Baumes nicht abnehmen, also Wenn wir aber das Array ändern und am Anfang ein Element einfügen, dann kann dies tatsächlich die Höhe verringern:

Finden Sie ein Array , so dass gilt.

Tip. Meine Beispiel-Arrays haben Größe 4 bzw. 5. Ich habe also ein Array der Länge 5, welches mir einen Baum der Höhe 2 gibt; wenn allerdings das erste Element im Array nicht da wäre, würde das restliche Array (der Länge 4) mir einen Baum der Höhe 3 (also schlechter) geben.

Übungsaufgabe 3.3.5 Wiederholen Sie die vorherige Aufgabe aber versuchen Sie, ein extremeres Ergebnis zu erreichen. Ich habe beispielsweise ein Array array gefunden, für das gilt In Worten, wenn Sie das erste Element wegnehmen, dann verdoppelt sich die Höhe des Baumes ungefähr. Finden Sie so ein Beispiel.
Übungsaufgabe 3.3.6 Im Geiste der vorherigen beiden Aufgaben, zeigen Sie, dass das Wegnehmen des Elements am Anfang des Arrays die Höhe des resultierenden BSTs nicht mehr als verdoppeln kann, also Hinweis. Das ist nicht ganz einfach. Ich empfehle Ihnen, Ihr Array als zu schreiben und dann mit die Elemente zu bezeichnen, die kleiner als sind (in der Reihenfolge, in der sie in vorkommen), und mit diejenigen, die größer als sind. Vergleichen Sie dann mit .
Beobachtung 3.3.2 Die Laufzeitkomplexität für find, insert, delete in einen BST ist begrenzt durch die Höhe des Baumes, also die Länge des längsten Pfades von der Wurzel zu einem Blatt.
Übungsaufgabe 3.3.7 Finden Sie eine "schlechte" Sequenz von insert-Operationen, die insgesamt quadratisch viele Schritte verursacht, also viele.

Die Herausforderung ist nun, die Implementierung von Binärbäumen so anzupassen, dass keine degenerierten Bäume entstehen, dass also idealerweise die Höhe des Baumes möglichst klein ist. Wie klein kann sie überhaupt sein? Wenn ein Baum Höhe hat, also die Länge eines Pfades von Wurzel zu einem Blatt höchstens Kanten hat, dann können wir die Knoten des Baumes in Level einteilen, wobei der Wurzel in Level 0 sitzt. Da jeder Knoten maximal zwei Kinder hat, gibt es in Level maximal Knoten. In Level gibt es nur noch Blätter. Also gibt es maximal innere Knoten, und somit ist , die Anzahl der gespeicherten Schlüssel-Wert-Paare, höchstens Wir lösen diese Ungleichung nach auf und erhalten

Beobachtung. 3.3.3 Sei ein BST mit inneren Knoten, also Schlüssel-Wert-Paaren. Dann gilt

Soweit die untere Schranke. Dieses Optimum von wird im Ernstfall nicht realistisch sein, aber vielleicht oder Ähnliches, können wir also erreichen? Ich werde im folgenden drei Methoden vorstellen, wie wir Tiefe erreichen können. Für alle sind insert und delete deutlich komplexer als für "naive" BSTs.

  • Treaps. Wir haben bereits gesehen, dass BSTs besonders schlecht werden, wenn die Elemente in geordneter Reihenfolge eingefügt werden. Was, wenn die Reihenfolge zufällig ist? Treaps simulieren eine zufällige Einfüge-Reihenfolge, indem sie jedem Schlüssel-Wert-Paar ein Gewicht zuordnen. "Leichte" Elemente sollen dann im BST höher stehen als "schwere". Dies garantiert, dass der BST immer so aussieht, als hätten wir die Elemente von leicht nach schwer sortiert eingefügt. Wenn wir schließlich die Gewichte zufällig wählen, sieht der BST so aus, als hätten wir die Elemente in zufälliger Reihenfolge eingefügt.

    Vorteil. Treaps sind recht einfach zu implementieren; wir müssen nur pro Element zusätzlich ein Gewicht speichern.

    Nachteil. Treaps sind randomisiert; alle oberen Schranken gelten also nur im Erwartungswert. Das heißt, Sie können rein theoretisch Pech haben und mit einem degenerierten Baum und hohen Suchzeiten enden. Die Laufzeitanalyse ist moderat kompliziert (wenn Sie keine Erfahrung mit Wahrscheinlichkeitsrechnung haben).

  • B-Bäume. Der Idealfall eines BSTs ist ja, dass er perfekt balanciert ist, also alle Blätter gleichen Abstand von der Wurzel haben. Das geht aber selbst theoretisch nur dann, wenn die Anzahl der Elemente die Form hat. Die Idee der B-Bäume ist, dass wir die Bedingung jeder innere Knoten hat genau zwei Kinder aufweichen in jeder innere Knoten hat zwei oder drei Kinder. Diese flexiblere Struktur erlaubt uns, jederzeit alle Blätter auf gleichem Niveau zu halten und somit immer eine perfekt balancierte Struktur zu unterhalten.

    Vorteil. Die Laufzeitanalyse ist extrem einfach. Die Höhe ist immer maximal .

    Nachteil. Die Implementierung ist etwas komplizierter.

  • Rot-Schwarz-Bäume (Red-Black-Trees). Dies sind wiederum "richtige" BSTs, in denen jeder innere Knoten genau zwei Kinder hat. Jeder innere Knoten bekommt eine Farbe Schwarz oder Rot, die gewissen Regeln unterworfen sind. Diese Regeln helfen uns, sicherzustellen, dass die Höhe des Baumes immer ist.

    Vorteil. Rot-Schwarz-Bäume sind BSTs, und dadurch ist der Code für find genau der Gleiche wie für naive BSTs. Die Laufzeitanalyse ist offensichtlich.

    Nachteil. Die Regeln für insert und delete müssen mehrere verschiedene Fälle von Knotenfärbungen beachten; das erschwert die Implementierung und auch das Verständnis.

Beachten Sie, dass in der Praxis weitere Vor- und Nachteile dazukommen können, die von Anwendungsfall zu Anwedungsfall variieren. Schwierigkeit der Laufzeitanalyse und Schwierigkeit der Implementierung sind für die Praxis auch nicht wirklich von Relevanz, da Sie ja meistens auf Implementierungen zurückgreifen können.