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.
http://www.informatik.uni-leipzig.de/~joe/
mailto:joe@informatik.uni-leipzig.de