Einfache binäre Bäume

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

Datentyp

Binäre Bäume sind eine Unterart von Bäumen, bei denen jeder Knoten ein Blatt (Leaf) oder eine Verzweigung (Fork) zu zwei weiteren Knoten (linker und rechter Teilbaum) ist. Bei den einfachen binären Bäumen (eine Untergattung der binären Bäume) werden Informationen nur in den Blättern gesichert.
Somit kann man für einfache binäre Bäume folgende Datentypendeklaration aufstellen:

data Btree a =   Leaf a
               | Fork (Btree a) (Btree a)
               deriving(Show)

In diesem Baum können, durch Einsatz der Typvariablen a, nun Informationen eines beliebigen Datentyps in einem Baum gespeichert werden. Das Beerben des Moduls Show ermöglicht es erstellte Bäume auszugeben rein textuell auszugeben.
Um nun einen Baum per Hand zu erstellen, können die Konstruktoren Leaf (für ein Blatt) und Fork (für eine Verweigung) genutzt werden. Beispielsweise sieht das so aus:

Diese Art der Baumausgabe ist allerdings nicht besonders übersichtlich. Später wird eine Funktion eingeführt, um einen Baum "graphisch" auszugeben.

 

Eigenschaften

Wie in der Einleitung erklärt hat jeder Baum spezielle Eigenschaften:

size :: Btree a -> Int
size (Leaf x)     = 1
size (Fork xt yt) = size xt + size yt

nodes :: (Btree a) -> Int
nodes (Leaf x)     = 0
nodes (Fork xt yt) = 1 + nodes xt + nodes yt

height :: (Btree a) -> Int
height (Leaf x)     = 0
height (Fork xt yt) = 1 + (max(height xt)(height yt))

smalleness :: (Btree a) -> Int
smalleness (Leaf x) = 0
smalleness (Fork xt yt) = 1 + (min(smalleness xt)(smalleness yt))

balanced :: (Btree a) -> Bool
balanced (Leaf x) = True
balanced (Fork xt yt) = max(height xt)(height yt) <= (min(smalleness xt)(smalleness yt) + 1)

Mit der Funktion size berechnet sich die Anzahl aller externer Knoten (Leafs).
Mit der Funktion nodes berechnet sich die Anzahl aller interner Knoten.
Mit der Funktion height berechnet sich die maximale Verzweigungslänge durch den Baum.
Mit der Funktion smalleness berechnet sich die minmale Verzweigungslänge durch den Baum.
Mit der Funktion balanced berechnet sich die Ausgewogenheit des Baumes.

Wie in Bäumen typisch erfolgt die Berechnung dieser Werte in rekursiver Art. Blätter sind das Ende der Rekursion. Ansonsten ergibt sich das Verhalten der Funktion aus der Beschreibung.

Zwischen der Anzahl interner und externer Knoten gilt für binäre Bäume folgendes Verhältnis:

Die Anzahl externer Knoten ist immer um eins größer als die Anzahl interner Knoten: size xt = nodes xt +1

 

Automatische Bearbeitung von binären Bäumen

mapBtree :: (a -> b) -> Btree a -> Btree b
mapBtree f (Leaf x) = Leaf (f x)
mapBtree f (Fork xt yt) = Fork(mapBtree f xt)(mapBtree f yt)

Die Funktion mapBtree entspricht im Prinzip der map Funktion für Listen. Sie ermöglicht es die Werte aller Blätter eines gegebenen Baumes mit einer gegebenen Funktion zu bearbeiten. Das Ergebnis einer Ausführung dieser Funktion ist ein neuer Baum mit den verarbeiteten Werten. Da der Ergebnistyp eine Typvariable ist, ist hier eine freie Verarbeitung und Umwandlung der gesicherten Werte möglich.
Für die Funktion mapBtree gelten folgende Gesetzmässigkeiten, die sich durch logische Schlussfolgerung bestätigen lassen:

 

foldBtree :: (a->b) -> (b->b->b) -> Btree a -> b
foldBtree f g (Leaf x) = f x
foldBtree f g (Fork xt yt) = g(foldBtree f g xt)(foldBtree f g yt)

Die Funktion foldBtree gibt dem Benutzer die Möglichkeit, neben der Verarbeitung der Daten in den Blättern, auch die Verarbeitung der Ergebnisse in den einzelnen Zweigen des Baumes angebenen Funktionen zu übergeben. Die übergebene Funktion f ist für die Verarbeitung der Daten in den Blättern zuständig und die übergebene Funktion g verarbeitet die Ergebnisse der beiden Teilbäume.

Mit der Foldfunktion lassen sich nun schon gegebene Funktionen neu definieren, zum Beispiel:

size2 :: (Btree a) -> Int
size2  = foldBtree (const 1) (+)

height2 :: (Btree a) -> Int
height2 = foldBtree (const 0) maxSubTree
          where maxSubTree m n = 1 + max m n

-- ... andere Funktionsumformungen möglich

Allerdings bringt einem diese Umsetzung der Funktionsdefinition, ausser der kürzeren Schreibweise, keinen Vorteil.

 

"Graphische" Ausgabe von Bäumen

thd3                :: (a,b,c) -> c
thd3 (_,_,x)         = x

drawBtree :: Show a => Btree a -> IO ()
drawBtree  = putStr . unlines . thd3 . pic
       where pic (Leaf a)  = (1,1,["-- "++show a])
             pic (Fork xt yt) = (hl+hr+1, hl+1, top pl ++ mid ++ bot pr)
                 where (hl,bl,pl) = pic xt
                       (hr,br,pr) = pic yt
                       top        = zipWith (++) (   replicate (bl-1) "   " ++ [" ,-"] 
                                                  ++ replicate (hl-bl) " | ")
                       mid        = ["-| "]
                       bot        = zipWith (++) (   replicate (br-1) " | " ++ [" `-"] 
                                                  ++ replicate (hr-br) "   ")

Diese Funktion zur "graphischen" Ausgabe eines Btrees wurde aus einer schon gegebenen Funktion für einen anderen Baum umgewandelt. Diese Funktion ermöglicht es einen Baum in Ascii Grafik auszugeben. 

    ,--- 1
 ,--|
 |  |  ,--- 2
 |  `--|
 |     `--- 3
-|
 |     ,--- 4
 |  ,--|
 |  |  `--- 5
 `--|
    |  ,--- 6
    `--|
       `--- 7
 
pic Fork (Leaf1) (Fork(Leaf 2)(Leaf 3))
    pic Leaf 1 
        = (1, 1, " --1") 
  pic Fork(Leaf 2)(Leaf 3) =
        pic Leaf 2 
            = (1, 1, " --2")
        pic Leaf 3 
            = (1, 1, " --3")
        = (3, 2, [" ,---2", "-| ", " `---3"])
= (4,2,[" ,---1", "-| "," |  ,---2", "`--| ","   `---3"])

Zur Erklärung dieser Funktion:

Die Funktion drawBtree erstellt den zu zeichnenden Baum durch Funktionskomposition diverser Funktionen:

Die Funktion pic stellt durch Rekursion eine Liste an Strings zusammen (für jede Zeile eine). Die zur Erstellung der Strings benötigten Hilfsinformationen werden durch die Funktion thd3 entfernt. Danach werden die verschiedenen Strings durch die Funktion unlines zu einem String mit Zeilenumbrüchen zusammengefasst. Dieser String wird dann durch die Funktion putStr ausgegeben.

Um die Funktionsweise der Funktion pic zu verstehen, ist es am einfachsten sich den Verlauf der einzelnen Rückgabewerte anzusehen. Für den oberen Baum (1,2,3) ( Fork (Leaf1) (Fork(Leaf 2)(Leaf 3))) sieht die Abfolge und die Rückgabewerte dann wie folgt aus:

 

Bäume und Listen

Bäume lassen sich in eine Liste überführen und auch aus Listen gewinnen: 

flatten :: (Btree a) -> [a]
flatten (Leaf x)     = [x]
flatten (Fork xt yt) = flatten xt ++ flatten yt

Die Funktion flatten "planiert" einen Baum in eine Liste, dabei geht er in preorder-Durchlaufsweise (von links nach rechts) vor. Die erstellte Liste des linken Teilbaumes wird mit der erstellten Liste des rechten Teilbaumes konkateniert.

mkBtree :: [a] -> Btree a
mkBtree (x:xs)
          | (m == 0)    = Leaf x
          | otherwise   = Fork (mkBtree ys)(mkBtree zs)
          where m       = (length (x:xs)) `div` 2
                (ys,zs) = splitAt m (x:xs)

Die Funktion mkBtree erzeugt aus einen gegebenen Liste einen ausgewogenen Baum. Diese Funktion halbiert, wenn die Liste mehr als ein Elemente besitzt, mit der aus Listen bekannten Funktion splitAt die gegebene Liste in zwei Teillisten und erstellt hieraus eine Verweigung. Besitzt die Liste nur ein Element, so wird dies als Blatt in den Baum eingefügt. Da die Liste immer halbiert wird, ist der Baum am Ende ausgeglichen. Diese Art der Baumerstellung benötigt n * log n Schritte, durch Optimierung ist aber auch ein Algorithmus möglich der einen solchen Baum in linearer Zeit erstellt.

Beispiele für mkBtree und flatten:

mkBtree[1,2,3,4,5,6,7] =


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


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

= [2,4,6,1,3,5,7]

 

balance :: (Btree a) -> (Btree a)
balance = mkBtree . flatten

Um einen nichtausgewogenen Baum in einen ausgewogenen umzuwandeln (zur Laufzeitoptimierung) kann man nun mit Hilfe der Funktionen flatten einen schon vorhandenen unausgewogenen Baum glätten und anschliessend wieder mit Hilfe der Funktion mkBtree in einen ausgewogenen Baum erstellen.

 

Weitere Beispielfunktionen

down :: Int -> (Btree a) -> (Btree Int)
down n (Leaf x) = Leaf n
down n (Fork xt yt) = Fork(down (n+1) xt) (down (n+1) yt)

depths :: (Btree a) -> (Btree Int)
depths = down 0

maxBtree :: (Ord a) => Btree a -> a
maxBtree (Leaf x) = x
maxBtree (Fork xt yt) = max (maxBtree xt) (maxBtree yt)

Die Funktion depths erstellt aus einem gegebenen Baum einen neuen Baum in dem alle Blätterwerte ihrer Tiefe im Baum entspricht.
Die Funktion maxBtree gibt den maximalen Inhalt eines Blattes zurück.

 

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