Vorlesung: Praxis der Funktionalen Programmierung


Bäume

Binäre Bäume mit Schlüsseln in Knoten

Siehe Quelltext.

Wir können die Liste der Werte aus den Knoten in Inorder-Reihenfolge berechnen (Quelltext).

Anwendung: Sortieren (Quelltext). Wir stellen einen (unbalancierten) Suchbaum her, und lesen diesen dann aus.

Dieses Sortierprogramm ist historisch wertvoll, es taucht als Beispiel auf in dem Artikel von McCarthy, in dem er seinerzeit (1960) die Programmiersprache LISP ankündigte.

Rotationen

Aufgabe (für binäre Standardbäume, Schlüssel in den Blättern): Rotiere den Baum einmal nach rechts, d. h. mache das am weitesten links stehende Blatt zur Wurzel.

Binäre Bäume mit Schlüsseln in Blättern

Selberbauen.

Rose Trees

(Quelltext). Beispielsweise kann man (2,3)-Bäume oder überhaupt b-Bäume als Rose trees auffassen, siehe jede Vorlesung über Datenstrukturen.

Rose Trees entstehen überhaupt als Suchbäume. (Beispiel PCP). Zum PCP siehe auch dieser Vortrag.


best viewed with any browser


http://www.informatik.uni-leipzig.de/~joe/ mailto:joe@informatik.uni-leipzig.de