Binärer Suchbaum – Akademischer Tag 7

Bei diesem akademischen Tag geht es, wie bereits versprochen, um den binären Suchbaum. Zur Illustration und Implementierung verwende ich Haskell, da man die aus dem Prequel bekannten Operationen sehr kompakt darstellen und somit auch erläutern kann.

Der binäre Suchbaum wird als binär bezeichnet, weil er einen Verzweigungsgrad von 2 besitzt, d.h. ein Knoten hat maximal zwei Kindknoten. Man unterscheidet i.d.R. zwischen zwei Arten von Knoten: Inneren Knoten und Blättern. Die Blätter haben im Gegensatz zu den inneren Knoten keine Kindknoten. Nachfolgendend enthalten nur die inneren Knoten einen Schlüssel sowie dessen assoziierten Wert. Auf der Schlüsselmenge muss jedoch eine Totalordnung ≤ definiert sein. Ein Beispiel ist die ≤-Relation auf den natürlichen Zahlen, weshalb wir in den Beispielen die natürlichen Zahlen als Schlüsselmenge wählen. Gegeben sei ein Baum T mit dem linken Teilbaum T₁ und dem rechten Teilbaum T₂. Es müssen dann folgende Eigenschaften gelten:

1. Alle Schlüssel in T₁ sind kleiner als die Wurzel von T.
2. Alle Schlüssel in T₂ sind größer als die Wurzel von T.
3. Diesen beiden Eigenschaften gelten außerdem für die beiden Teilbäume T₁ und T₂ und deren Teilbäume usw.

Die folgende Grafik zeigt einen solchen Suchbaum, wobei die inneren Knoten mit ihren Schlüsseln (d.h. Zahlen) gekennzeichnet sind und die Blätter durch die schwarzen Quadrate dargestellt werden.

Anhand dieser Eigenschaften lässt sich die Strategie zum Traversieren des Baums erklären. Beginnen wir aber erstmal mit der Definition eines binären Baums:

> data Tree k a = Node { key :: k, val :: a, left :: Tree k a, right :: Tree k a }
>               | Leaf
>               deriving Show

Ein Baum vom Typ Tree k a ist entweder ein Knoten (Node), der aus Schlüssel (key) vom Typ k, Wert (val) vom Typ a, einem linken (left) und rechtem (right) Teilbaum vom Typ Tree k a besteht, oder ein Blatt (Leaf).

> insert :: Ord k => k -> a -> Tree k a -> Tree k a
> find :: Ord k => k -> Tree k a -> Maybe a
> delete :: Ord k => k -> Tree k a -> Tree k a

Es sind drei Funktion insert, find und delete mit folgenden Parametern und Rückgabewerten:

• insert:
  • Kontext: Auf k existiert eine Totalordnung.
  • Parameter: Schlüssel vom Typ k, Wert vom Typ a und ein Baum vom Typ Tree k a.
  • Rückgabewert: Baum vom Typ Tree k a.
• find:
  • Kontext: Auf k existiert eine Totalordnung.
  • Parameter: Schlüssel vom Typ k, Baum vom Typ Tree k a.
  • Rückgabewert: Möglicherweise ein Wert vom Typ a, d.h. ein Wert vom Typ Maybe a.
• delete:
  • Kontext: Auf k existiert eine Totalordnung.
  • Parameter:  Schlüssel vom Typ k, Baum vom Typ Tree k a.
  • Rückgabewert: Baum vom Typ Tree k a.

Beginnen wir mit der einfachsten Funktion: Dem Auffinden eines Schlüssels.

> find x Leaf = Nothing
> find x (Node { key = y, val = value, left = l, right = r })
>    | x <= y && y <= x = Just value
>    | x <= y = find x l
>    | y <= x = find x r

Zuerst wird durch das Pattern-Matching überprüft, ob wir uns in einem inneren Knoten oder einem Blatt befinden. Befinden wir uns in einem inneren Knoten gibt es drei Möglichkeiten:

1. Der Schlüssel der Wurzel (y) ist gleich dem gesuchten Schlüssel (x): Der gefundene Wert value wird als Just value zurückgegeben, damit er vom Typ Maybe a ist.
2. y ist kleiner als x, d.h. x befindet sich höchstens im linken Teilbaum, weshalb die Suche dort fortgesetzt wird.
3. y ist größer als x, d.h. x befindet sich höchstens im rechten Teilbaum, weshalb die Suche dort fortgesetzt wird.

Irgendwann trifft man entweder auf den gesuchten Schlüssel oder man erreicht ein Blatt. Im letzteren Fall wird dann Nothing (vom Typ Maybe a) zurückgegeben, was bedeutet, dass der Schlüssel nicht im Baum gefunden wurde.

Die Funktion zum Einfügen ist sehr ähnlich gestrickt.

> insert x v Leaf = Node { key = x, val = v, left = Leaf, right = Leaf }
> insert x v t@(Node { key = y, left = l, right = r })
>    | x <= y && y <= x = t { val = v }
>    | x <= y = t { left = insert x v l }
>    | y <= x = t { right = insert x v r }

Eingefügt wird ein neuer Knoten erst, wenn man auf ein Blatt stößt, welches dann durch einen neuen Knoten mit zwei Blättern ersetzt wird. Vor dem eigentlich Einfügen muss jedoch eine Suche ausgeführt werden, damit man weiß. wo der Knoten in die Struktur eingefügt werden muss. Hierbei können wieder drei Fälle auftreten:

1. Der Schlüssel der Wurzel (y) ist gleich dem Schlüssel des einzufügenden Elements (x): Der Wert in diesem Knoten wird lediglich durch einen neuen ersetzt (v).
2. x ist kleiner als y: Der Wert v (mit dem Schlüssel x) wird in den linken Teilbaum des aktuellen Baums (t) eingefügt.
3. x ist größer als y: Der Wert v (mit dem Schlüssel x) wird in den rechten Teilbaum des aktuellen Baums (t) eingefügt.

Am kniffligsten wird die Funktion zum Löschen eines Knotens.

> delete x Leaf = Leaf
> delete x t@(Node { key = y, left = l, right = r })
>    | x <= y && y <= x = case l of
>       Leaf -> r
>       _    -> append l r
>    | x <= y = t { left = delete x l }
>    | y <= x = t { right = delete x r }
>  where append Leaf r = r
>        append t@(Node { right = r' }) r = t { right = append r' r }

Das Löschen aus einem Baum, das nur aus einem Blatt besteht, verändert nichts an diesem Baum. Wird die Löschfunktion bei einem inneren Knoten ausgeführt sind wieder die drei Fälle möglich. Wenn für den zu löschenden Schlüssel x und dem Schlüssel der Wurzel y entweder x < y oder y < x gilt, dann wird der x aus dem linken bzw. dem rechten Teilbaum des aktuellen Baums t gelöscht. Wurde der Knoten, der gelöscht werden soll, gefunden, gibt es zwei Fälle, die beide dazu führen, dass aus t ein neuer Baum entsteht, der mit Ausnahme von x die gleichen Elemente enthält:

1. Der linke Teilbaum (l) von t ist ein Blatt: Der Baum t wird durch r ersetzt.
2. Der linke Teilbaum (l) von t ist ein innerer Knoten: Der Baum t wird durch den Baum ersetzt, der entsteht, wenn man das am weitesten rechts liegende Blatts (in l) durch r ersetzt.

Die zuletzt genannte Ersetzung ist möglich, da bekannt ist, dass jeder Schlüssel des rechten Teilbaums (r) größer als jeder Schlüssel im linken Teilbaum (l) ist und man deshalb beim Einfügen eines Schlüssels aus r immer beim am weitesten rechts liegenden Blatts in l einfügen müsste. Da der rechte Teilbaum bereits ein binärer Baum ist, kann man sich also den Aufwand sparen, jedes Element einzeln in den linken Teilbaum einzufügen.

Zum Schluss erfolgt noch die Komplexitätsbetrachtung. Bereits im vorangegangenen Artikel wurde festgestellt, dass das Suchen in einem Baum in O(h) möglich ist, wobei h die Höhe darstellt. Aus der Höhe und dem Verzweigungsgrad 2 können wir berechnen, wie viele Knoten der Baum hat, wenn die Blätter alle auf einer Ebene sind: n = 2^h, woraus die Gleichung h = log₂(n) folgt. D.h. das Suchen in einem solchen Baum dauert O(log₂(n)) bzw. O(log n) Schritte, da die Basis bei der Komplexitätsbetrachtung keinen Unterschied macht. In diesem Fall ist der Baum balanciert, d.h., dass die Höhe der Teilbäume sich um maximal 1 unterscheidet. Der binäre Suchbaum ist jedoch nicht balanciert, da die Struktur des Baums von der Reihenfolge, in der die Schlüssel eingefügt werden, beeinflusst werden. Z.B. stellt das Einfügen einer sortierten Liste stellt das Worst-Case-Szenarion für einen binären Suchbaum dar, da die Elemente immer ganz rechts angefügt werden, aber niemals an einen linken Teilbaum. Letztlich entsteht daraus eine verkettete Liste, die mit O(n) zu Buche schlägt. Um die Balance des Baums zu garantierten, kann er durch Rotationen erweitert erden, womit letztendlich der AVL-Baum entsteht.

Anmerkung: Wenn man den Text dieses Artikels kopiert, in eine .lhs-Datei speichert und sie anschließend mit dem GHCi startet, kann man sich die Funktionsweise durch Beispiele veranschaulichen.