Binäre Suchbäume

ZURÜCK ---- INHALTSVERZEICHNIS ---- WEITER

Datentyp

Eine weitere mögliche Nutzung der binären Bäume sind binäre Suchbäume. Diese sind, ihrem Namen entsprechend, besonders geeignet zum Suchen. Daher bietet es sich an diese Bäume zur Representation von Mengen bzw. Listen, in denen gesucht werden soll, einzusetzen. Das Prüfen, ob ein Element in einer Liste bzw. in einer Menge enthalten ist, entspricht einer Suche in solch einem Baum. Um in einem Baum zu suchen, muss dieser entsprechend aufgebaut und geordnet sein.

Für einen binären Suchbaum (auch "labelled binary trees" genannt) soll folgende Datendefinition gelten:

data (Ord a =>) Stree a =   Null
                          | Fork (Stree a) a (Stree a)
                          deriving(Show)

An der Datendefinition fällt sofort auf das dieser binäre Suchbaum keine Blätter mehr besitzt. Diese werden durch einen leeren Unterbaum ersetzt (Null). Die bisher in den Blättern gesicherten Informationen werden in die internen Knoten zwischen die beiden Unterbäume verschoben. Diese Anordnung soll die Ordnung des Baumes beschreiben, die Werte im linken Unterbaum sind kleiner gleich dem Wert des Knotens, der wiederum kleiner gleich aller Werte im rechten Unterbaum ist.

Da dieser Baum entsprechend der darin gesicherten Daten geordnet sein soll, müssen die gesicherten Daten orderbar sein. Daher können nur Typen der Typklasse Ord genutzt werden.

Damit der Baum nachher geordnet ist und bleibt, ist beim Erstellen sowie beim Bearbeiten darauf zu achten, dass die Ordnung beibehalten bleibt. Dieses kann man zum Beispiel durch Definieren eines abstrakten Datentypes mit den zugehörigen Bearbeitungsfunktionen erreichen. Dieses ist allerdings schon Thema eines anderen Vortrags, daher soll in den folgenden Bearbeitungsfunktionen so darauf geachtet wird, das die Ordnung nicht verletzt wird.

 

Bäume und Listen

Wie in den anderen beiden Beispielen binärer Bäume, so soll auch dieses eine Funktion besitzen einen Baum in eine (geordnete) Liste zu überführen und andersum eine (ungeordnete) Liste in einen geordneten Baum zu überführen.

flatten :: (Ord a) => Stree a -> [a]
flatten Null = []
flatten (Fork xt x yt) = flatten xt ++ [x] ++ flatten yt

Ein geordneter binärer Baum kann wie bei den Beispielen vorher in eine Liste überführt werden. Dazu wird in inorder-Durchlaufweise vorgegangen. An die aus dem linken Teilbaum erstellte Liste, wird der Inhalt des Knotens und die aus dem rechten Teilbaum erstellte Liste konkateniert.

 

partition :: (a ->Bool) -> [a] -> ([a],[a])
partition p xs = (filter p xs, filter (not. p) xs)

mkStree :: (Ord a) => [a] -> Stree a
mkStree [] = Null
mkStree (x:xs) = Fork (mkStree ys) x (mkStree zs)
               where (ys,zs) = partition (<=x) xs

Das Erstellen eines Baumes aus einer Liste war bisher relativ trivial, da aber bei dieser Baumart die Sematik der Ordnung der Daten gewahrt bleiben soll, ist ein etwas größerer Aufwand notwendig, um dieses sicherzustellen. Aus der Liste wird das erste Element genommen, dieses repräsentiert den Inhalt des neu zu erstellenden Knotens. Aus der Restliste werden mittels der Funktion partition zwei Listen erzeugt, die alle Elemente enthalten, die kleiner gleich dem aktuellen Knotenelement sind und alle Elemente enthalten die größer als das aktuelle Knotenelement sind. Mit diesen beiden Listen werden auf die gleiche Art die Unterbäume des Knotens erzeugt.

Dabei ist gleich anzumerken, das der erzeugte Baum nicht ausgewogen ist. Wird zum Beispiel eine sortierte aufsteigende Liste übergeben, so wird ein rechtslastiger Baum erzeugt, dessen linke Unterbäume immer leer sind. Um einen Suchbaum effizient nutzen zu können, müsste diese Funktion noch verbessert werden.

Das Erstellen eines einfachen binären Baumes läuft optimiert in linearer Zeit ab, währenddessen die optimierteste Version von mkStree n*log n Schritte benötigt

 

sort_list :: (Ord a) => [a] -> [a]
sort_list = flatten . mkStree

Mit Hilfe dieser gegebenen Funktionen kann nun ein Algorithmus zum Sortieren von Listen aufgestellt werden. Dabei wird eine gegebene Liste in einen geordneten Baum überführt. Beim Glätten des Baumes durch die Funktion flatten ensteht dann eine geordnete Liste. "Entfernt" man die Erstellung eines Baumes so ist diese Art des Sortierens das quicksort-Verfahren.

 

Eigenschaften

Wie bei den anderen Bäumen können auch zu diesem Baum Eigenschaften ausgegeben werden. Die Metriken eines Baumes (Hoehe usw.) bestimmt sich fast wie bei den vorherigen Beispielen binärer Bäume. Allerdings müsste hierbei noch eine Anpassung an den neuen Datentypen geschehen. Für die binären Suchbäume können nun einige neue Eigenschaften bestimmt werden:

member :: (Ord a) => a -> Stree a -> Bool
member k Null = False
member k (Fork xt x yt)
       |k<x       = member k xt
       |k==x      = True
       |otherwise = member k

Da wir einen geordneten Baum haben, ist es nun leichter nach einem bestimmten Element in der Liste zu suchen (Elementtest). Die Funktion member durchsucht den Baum und je nachdem ob der gesuchte Eintrag kleiner oder größer als der in einem Knoten gespeicherte Wert ist, wird dess linker oder rechter Teilbaum weiter durchsucht. Entspricht das gesuchte Element dem Inhalt des Knotens war die Suche erfolgreich, stößt man bei der Suche auf einen leeren Baum, so wurde das gesuchte Element nicht gefunden.

 

lordered :: (Ord a) => a -> [a] -> Bool
lordered k [] = True
lordered k (x:xs)
       |k<=x       = lordered x xs
       |otherwise  = False

start_lordered :: (Ord a) => [a] -> Bool
start_lordered [] = True
start_lordered (x:xs) = lordered x xs

tordered :: (Ord a) => Stree a -> Bool
tordered = start_lordered . flatten

Mit Hilfe einer weiteren Funktion kann überprüft werden, ob ein übergebener Baum auch geordnet ist. Dazu wird der Baum mittels der Funktion tordered geglättet und die erstellte Liste wird auf aufsteigende Werte überprüft. Diese Prüfung wird von der Funktion start_lordered gestartet. Dieser Algorithmus kann sicherlich noch verbessert werden, aber für die reine Überprüfung funktioniert er.

 

Einfügen und Löschen

Um mit einem Baum zu arbeiten, muss es möglich sein Elemente aus dem Baum zu entfernen und hinzuzufügen. Bei den binären Suchbäumen ist darauf zu achten, dass die Ordnung des Baumes gewahrt bleibt. 

insert :: (Ord a) => a -> Stree a -> Stree a
insert n Null = Fork Null n Null
insert n (Fork xt x yt)
       | n<x        = Fork (insert n xt) x yt
       | n>x        = Fork xt x (insert n yt)
       | otherwise  = Fork xt x yt

Beim Einfügen wird aus dem gegebenen Baum ein neuer Baum erstellt. Dabei wird das neue Element gemäß der Ordnung eingefügt. Ist das Element kleiner als das Element im Knoten wird er im linken Unterbaum eingefügt. Ist er größer wird er im rechten Unterbaum eingefügt. Ist das Element gleich dem Element des Knotens wird in diesem Falle kein neues Element erstellt, sondern der bisherige Baum übernommen. Dies ist gegensätzlich zu der mkStree Funktion, die auch gleiche Elemente im Baum zulässt.

       ,-
    ,--1
    |  `-
 ,--2
 |  |  ,-
 |  `--4
 |     `-
-5
 |     ,-
 |  ,--6
 |  |  `-
 `--7
    |  ,-
    `--8
       `- 
insert 3 =

       ,-
    ,--1
    |  `-
 ,--2
 |  |     ,-
 |  |  ,--3
 |  |  |  `-
 |  `--4
 |     `-
-5
 |     ,-
 |  ,--6
 |  |  `-
 `--7
    |  ,-
    `--8
       `-

 

Das Löschen eines Elements aus einem Baum ist schon etwas komplexer:

emptyTree :: (Ord a) => Stree a -> Bool
emptyTree Null = True
emptyTree (Fork xt x yt) = False

splitTree :: (Ord a) => Stree a -> (a,Stree a)
splitTree Null = error "split of an empty tree"
splitTree (Fork xt z yt) 
        | emptyTree xt  = (z,yt) 
        | otherwise     = (v, Fork wt z yt)
            where (v,wt) = splitTree xt

headTree :: (Ord a) => Stree a -> a
headTree = fst . splitTree

tailTree :: (Ord a) => Stree a -> Stree a
tailTree = snd . splitTree

join :: (Ord a) => Stree a -> Stree a -> Stree a
join xt yt
      | emptyTree yt  = xt
      | otherwise     = Fork xt (headTree yt) (tailTree yt)

delete :: (Ord a) => a -> Stree a -> Stree a
delete n Null = Null
delete n (Fork xt x yt)
       | n<x        = Fork (delete n xt) x yt
       | n>x        = Fork xt x (delete n yt)
       | otherwise  = join xt yt

Beim Löschen (delete) eines Elements aus einem Baum, wird wieder ein neuer Baum erstellt. Beim Löschen können zwei Fälle auftreten:

Dieses Zusamenführen von zwei Bäumen durch die Funktion join kann auf diverse verschiedene Arten erfolgen. Diese Funktion muss der Bedingung flatten (join xt yt) = flatten xt ++ flatten yt genügen. In Worten muss also der zusammengeführte Baum beim Glätten die gleiche Liste erzeugen, wie die zusammengeführten zu Listen geglätteten Teilbäume. In diesem Beispiel der Funktion join wird wie folgt vorgegangen:

       ,-
    ,--1
    |  `-
 ,--2
 |  |  ,-
 |  `--4
 |     `-
-5
 |     ,-
 |  ,--6
 |  |  `-
 `--7
    |  ,-
    `--8
       `- 
delete 5 = 


       ,-
    ,--1
    |  `-
 ,--2
 |  |  ,-
 |  `--4
 |     `-
-6
 |  ,-
 `--7
    |  ,-
    `--8
       `-

Ist der rechte übergebene Baum leer dann wird der linke übergebene Baum als Ergebnis zurückgegeben. Ist der rechte Baum belegt, so wird das kleinste Element dieses Baumes (head) als Wurzel des neu erstellten Baumes genutzt. Für diese Wurzel bilden der linke übergebene Baum und der tail des rechten übergebenen Baumes die beiden neuen Unterbäume.

Head und tail eines Baumes werden durch die Funktion splitTree erstellt. Diese gibt ein Paar mit dem Head und des Restbaumes zurück. Beim Aufruf dieser Funktion darf kein leerer Baum übergeben werden, da dies ansonsten zu einer Fehlermeldung führt. Diese Funktion traversiert solange durch den Baum bis der linke Unterbaum leer ist, das Element dieses Baumes ist der Kopf des Baumes (kleinstes Element). Beim Traversieren zu diesem Element wird aus den anderen Elementen ein Restbaum erstellt.

 

ZURÜCK ---- INHALTSVERZEICHNIS ---- WEITER