Welcher selbstbalancierende Baum ist am einfachsten in der funktionalen Programmierung?

Question

Ich entwerfe einen selbstabgleichenden Baum in Haskell. Als Übung und weil es schön ist, in der Hand zu haben.

Zuvor in C und Python bevorzugte ich Treaps und Splay Trees aufgrund ihrer einfachen Balanceregeln. Ich mochte R/B-Bäume immer nicht, da sie mehr Arbeit als sie wert schienen.

Jetzt, aufgrund der funktionalen Natur von Haskell, scheinen sich die Dinge geändert zu haben. Ich kann eine R/B-Einfügefunktion in 10 Codezeilen schreiben. Treaps auf der anderen Seite müssen umschlossen werden, um den Zufallszahlengenerator zu speichern, und Splay Trees sind von oben nach unten ein Ärgernis.

Also frage ich, ob Sie Erfahrung mit anderen Arten von Bäumen haben? Welche sind besser geeignet, die Mustererkennung und die Top-down-Funktion von funktionalen Sprachen zu nutzen?

Answer 1

Ok, ich denke, es gab nicht viele Referenzen oder Nachforschungen zur Beantwortung dieser Frage. Stattdessen habe ich mir die Zeit genommen, deine verschiedenen Ideen und Bäume auszuprobieren. Ich habe nicht viel besseres gefunden als RB-Bäume, aber vielleicht ist das nur ein Such-Bias.

Der RB-Baum kann (insertion) ausgeglichen mit vier einfachen Regeln, wie shown by Chris Okasaki:

balance T (T R (T R a x b) y c) z d = T R (T B a x b) y (T B c z d) 
balance T (T R a x (T R b y c)) z d = T R (T B a x b) y (T B c z d) 
balance T a x (T R b y (T R c z d)) = T R (T B a x b) y (T B c z d) 
balance T a x (T R (T R b y c) z d) = T R (T B a x b) y (T B c z d) 
balance T a x b = T B a x b 

AVL-Bäume können in einer ähnlichen Art und Weise Musteranpassungs ausgeglichen werden. Allerdings sind die Regeln komprimieren nicht so gut:

balance T (T (T a x b dx) y c (-1)) z d (-2) = T (T a x b dx) y (T c z d 0) 0 
balance T a x (T b y (T c z d dz) 1) 2 = T (T a x b 0) y (T c z d dz) 0 
balance T (T a x (T b y c 1) 1) z d (-2) = T (T a x b -1) y (T c z d 0) 0 
balance T (T a x (T b y c (-1)) 1) z d (-2) = T (T a x b 0) y (T c z d 1) 0 
balance T (T a x (T b y c _) 1) z d (-2) = T (T a x b 0) y (T c z d 0) 0 
balance T a x (T (T b y c 1) z d (-1)) 2 = T (T a x b -1) y (T c z d 0) 0 
balance T a x (T (T b y c (-1)) z d (-1)) 2 = T (T a x b 0) y (T c z d 1) 0 
balance T a x (T (T b y c _) z d (-1)) 2 = T (T a x b 0) y (T c z d 0) 0 
balance t = t 

Wie AVL Bäume Nähte in der Regel schlechter als RB Bäume in Betracht gezogen werden, sind sie wahrscheinlich nicht wert, die zusätzlichen Aufwand.

AA Bäume könnten theoretisch ausgeglichen schön und leicht von:

balance T n (T n a x b) y c = T n a x (T n b y c) -- skew 
balance T n a x (T n b y (T n c z d)) = T (n+1) (T n a x b) y (T n c z d) --split 
balance T n a x b = T n a x b 

Aber leider Haskell nicht wie die Überlastung der n. Es ist möglich, dass eine weniger standardisierte Implementierung von AA-Bäumen, die keine Ränge verwenden, sondern etwas, das R und B ähnlicher ist, gut funktionieren würde.

Splay-Bäume sind schwierig, da Sie sich auf einen einzelnen Knoten anstatt auf die statische Struktur des Baums konzentrieren müssen. Es kann durch merging insert and splay erfolgen.

Treasures sind auch in einer funktionalen Umgebung unruhig, da Sie keinen globalen Zufallsgenerator haben, sondern Instanzen in jedem Knoten behalten müssen.Dies kann durch leaving the task of generating priorities to the client angegangen werden, aber selbst dann können Sie keinen Prioritätsvergleich mit Mustervergleich durchführen.

Answer 2

Wie Sie sagen Red Black Bäume sind nicht so schwer zu benutzen. Hast du finger trees a look angegeben? Sie könnten daran interessiert sein, Ihre Basisdatenstruktur mit etwas wie einem zipper. zu erweitern. Ein anderer Baum, den Sie vielleicht interessant finden, ist der AA tree es ist eine Vereinfachung von Red Black Trees.

Answer 3

Es ist das, das bereits implementiert ist.

Es gibt feine Implementierungen in Haskell von ausgeglichenen Bäumen wie Data.Map und Data.Set. Erfüllen sie nicht deine Bedürfnisse? Nicht neu implementieren, wiederverwenden.

Answer 4

Die OCaml-Standardbibliothek verwendet einen AVL-Baum für den Funktor map. Es scheint, als ob es einfacher ist, als ein RB-Baum zu implementieren, wenn Sie eine remove Operation einschließen.