Rose Trees

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

Datentyp

Bei den Rose Trees, zu deutsch Rhododendron, wird die bisher binäre Struktur beiseite gelegt und es wird das Erzeugen eines Baumes mit beliebig vielen Ästen pro Knoten ermöglicht. Eine mögliche Datentypdefinierung sieht wie folgt aus:

data Rtree a = Node a [Rtree a]
               deriving(Show)

Diese Datendefinition sieht mindestens einen Knoten mit einer beliebig langen Liste von Unterknoten vor. Dabei werden Knoten ohne weitere Unterbäume als externe Knoten und Knoten mit mindestens einem Unterbaum als interne Knoten bezeichnet.

Hierzu einige Beispiele:

Ein Baum dieser Art ist endlich, wenn jeder Unterbaum endlich ist. Er besitzt die Breite w, die der größten Breite eines der internen Knoten entspricht. Haben alle internen Knoten die gleiche Anzahl an Unterbäumen, so wird dieser Rose-Tree auch k-ary genannt.
Zum Beispiel werden die binären Bäume als 2-ary bezeichnet. Diese sind ein Sonderfall der Rose-Trees, mit der Einschränkung das jeder interne Knoten genau zwei Unterbäume besitzt.
Als perfekten Rose-Tree werden Bäume bezeichnet deren externe Knoten alle die gleiche Tiefe haben.

 

Eigenschaften

Das Berechnen von Eigenschaften dieser Bäume wird, durch die neue "Freiheit" einem Knoten einige beliebige Anzahl an Unterbäumen zuzuordnen, etwas komplizierter. Da die Unterbäume in Listenformat aufgeführt sind, werden die Bearbeitungsfunktionen eine Mischung aus Baumfunktionen und Listenfunktionen sein, wie die folgenden Beispiele zeigen:

size :: Rtree a -> Int
size (Node x xts) = 1 + sum(map size xts)

height :: Rtree a -> Int
height (Node x xts) = 1 + maxlist(map height xts)
                      where maxlist = foldl (max) 0

Die Berechnung der Größe des Baumes (size) zeigt dieses Zusammenarbeiten von Listen und Baumfunktionen. Die Funktion mappt sich selber auf die Liste der Unterbäume und addiert 1 auf dieses Ergebnis.

Die Funktion height, zur Berechnung der längsten Verästelung in dem übergebenen Baum, arbeitet zudem noch mit der foldl Funktion der Listen. Zur Berechnung der Höhe wird 1 zu dem maximalen Ergebnis der height-Funktion der Liste an Unterbäumen zuaddiert.

Die Größe und die Höhe der Rose-Trees ist, wie die Funktionen zeigen, immer größer als 0.

 

Automatische Bearbeitung von Rose Trees

Bisher kennen wir die automatische Bearbeitung von Bäumen nur bei binären Bäumen. Etwas erweitert kann diese Funktionalität auch auf die Rose Trees übernommen werden:

mapRtree :: (a -> b) -> Rtree a -> Rtree b
mapRtree f (Node x xts) = Node (f x) (map (mapRtree f) xts)

Die Funktion mapRtree bearbeitet die Werte der Knoten des übergebenen Baumes und erstellt daraus einen neuen Baum. Dazu wird eine Bearbeitungsfunktion übergeben, deren Ergebnistyp der neue Datentyp der Knotenwerte ist. Daher erklärt sich die Funktionsweise der Funktion wie folgt. Es wird ein neuer Knoten erstellt. Der Wert dieses Knotens ergibt sich aus der Ausführung der übergebenen Funktion auf den bisherigen Knoteninhalt. Die Liste an Unterbäumen dieses neuen Knotens wird durch Ausführung der mapRtree Funktion auf alle Unterbäume durch die Funktion map erstellt.

 

foldRtree :: (a->[b]->b) -> Rtree a -> b
foldRtree f (Node x xts) = f x (map (foldRtree f) xts)

Die fold-Funktion dieser Baumgattung wird auf ähnliche Art und Weise ausgeführt. Dabei fällt auf, das dieser fold-Funktion im Vergleich zu den anderen nur eine Funktion übergeben wird. Daher sind die Parameter dieser Funktion entsprechend anzupassen.

Mit Hilfe der fold Funktion können nun auch andere Funktionen durchgeführt werden: 

size2 :: Rtree a -> Int
size2 = foldRtree f
        where f x ns = 1 + sum ns

maxRtree :: (Ord a, Num a) => Rtree a -> a
maxRtree = foldRtree f
           where f x ns  = max x (maxlist ns)
                 maxlist = foldl max 0

mapRtree2 :: (a -> b) -> Rtree a -> Rtree b
mapRtree2 f = foldRtree (Node . f)

 

Depth-First and Breadth-First

flatten :: Rtree a -> [a]
flatten (Node x xts) = x: concat(map flatten xts)

Beim Glätten eines Baumes wird bei dieser Funktion in einer sogenannten Depth-First Reihenfolge vorgegangen. Das bedeutet das der linkstmögliche Baum zuerst ganz bis zum Ende durchgelaufen wird, bevor wieder ein Schritt in die Breite gemacht wird.

Ganz im Gegensatz dazu ist das Vorgehen in den sogenannten Breadth-First Reihenfolge. Dabei wird zuerst jeder Level des Baumes abgearbeitet bevor wieder ein Schritt in die Tiefe gemacht wird. Dieses Vorgehen hat Vorteile als auch Nachteile, zum Beispiel können auch infinite Bäume ausgegeben werden, allerdings ist der Platzverbrauch gegenüber depth-first sehr viel größer da die kompletten Level jeweils gesichert werden müssen.

 

Rtrees und Btrees

Das Umwandeln von Rose Trees in einen binären Baum und zurück entspricht in etwa den Funktion uncurried und curried.

toB :: Rtree a -> Btree a
toB(Node x xts) = foldl Fork(Leaf x) (map toB xts)

Dazu werden all Unterbäume zu binären Bäumen umgewandelt und diese Bäume werden mit Hilfe der foldl-Funktion zu einem einzelnen Baum umgewandelt.

Die umgekehrte Funktion aus einem binären Baum einen Rtree zu machen ist allerdings schon sehr viel aufwendiger, da hierbei natürlich davon ausgegangen werden soll das ein zu einem binären Baum umgewandelter Rose-Tree bei der Rückumwandlung wieder der gleiche ist. Daher ist diese Funktion hier nicht angegeben.

 

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