Erweiterte binäre Bäume

• Datentyp
• Einsatz

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

Datentyp

Die einfachen binären Bäume haben ihre Informationen bisher nur in den Blättern gesichert. Bei den erweiterten binären Bäumen soll die Einschränkung entfernt werden und die Informationen sollen in jedem Knoten speicherbar sein. Diese Art von Bäumen wird von mehreren wichtigen Anwendungen genutzt. Daraus ergibt sich folgende neue Datentypdefiniton

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

Der Wert des internen Knoten ist auf Int festgelegt ist, da dieses für den späteren Einsatzzweck dienlich sein wird.

Für diese Art des binären Baumes lassen sich von funktionaler Seite aus fast alle Funktionen der einfachen binären Bäume wiederverwenden, allerdings müssen die Definitionen noch dem neuen Datentyp angepasst werden.

Einsatz

Diese Art des erweiterten Baumes soll nun einen indizierten Zugriff auf die Elemente des Baumes zulassen, wie die Funktion !! einen indizierten Zugriff auf die Listenelemente zulässt.
Dazu müssen die Werte der internen Knoten allerdings auf die Art und Weise speziell belegt sein, das jeder interne Knoten die Anzahl an untergeordneten Blättern besitzt. Um dieses zu gewährleisten wird ein neuer Konstruktor eingeführt...

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

fork :: Etree a -> Etree a -> Etree a
fork xt yt = Fork n xt yt
             where n = lsize xt

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

Um besser verstehen zu können, hier ein Beispielbaum mit den entsprechenden Indizes....

drawEtree (mkEtree[1,2,3,4,5,6,7,8,9]):
       ,--- 1
    ,--| 1
    |  `--- 2
 ,--| 2
 |  |  ,--- 3
 |  `--| 1
 |     `--- 4
-| 4
 |     ,--- 5
 |  ,--| 1
 |  |  `--- 6
 `--| 2
    |  ,--- 7
    `--| 1
       |  ,--- 8
       `--| 1
          `--- 9  

Mit dieser Grundlage kann nun eine Abfragefunktion geschaffen werden mit der es möglich ist einen speziellen Knoten indiziert abzufragen, dabei ist zu bedenken dass das erste Element mit Index 0 abgefragt wird. Im anderen Fall wird eine Fehlerfunktion aufgerufen.

retrieve :: Etree a -> Int -> a
retrieve (Leaf x) y
			| y == 0    = x
			|otherwise  = error "Node not available"
retrieve (Fork m xt yt) k
		    |k<m       = retrieve xt k
		    |otherwise  = retrieve yt (k-m)n)

Diese Art der des indizierten Zugriffs benötigt Schritte proportional zu log n, während !! Schritte proportional zu n. Je nach Anzahl an Zugriffen lohnt sich dann irgendwann das Erstellen eines erweiterten binären Baumes mit Hilfe von mkAtree zum indizierten Zugriff.

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