Welchen selbstausgleichenden Binärbaum würden Sie empfehlen?

18

Ich lerne Haskell und mache als Übung binäre Bäume. Nachdem ich einen regulären Binärbaum erstellt habe, möchte ich ihn so anpassen, dass er sich selbst ausbalanciert. So:

  • Welches ist am effizientesten?
  • Welches ist am einfachsten zu implementieren?
  • Welches wird am häufigsten verwendet?

Aber entscheidend, welches empfehlen Sie?

Ich nehme an, das gehört hierher, weil es offen für Diskussionen ist.

haskell functional-programming data-structures binary-tree dan_waterworth
quelle
In Bezug auf Effizienz und einfache Implementierung sind die allgemeinen Effizienzen
klar

Antworten:

15

Ich würde empfehlen, mit einem Rot-Schwarz-Baum oder einem AVL-Baum zu beginnen .

Der rot-schwarze Baum kann schneller eingefügt werden, der AVL-Baum hat jedoch eine leichte Kante für die Suche. Der AVL-Baum ist wahrscheinlich ein bisschen einfacher zu implementieren, aber nicht so sehr auf der Grundlage meiner eigenen Erfahrung.

Der AVL-Baum stellt sicher, dass der Baum nach jedem Einfügen oder Löschen ausgeglichen wird (kein Unterbaum hat einen Ausgleichsfaktor von mehr als 1 / -1, während der Rot-Schwarz-Baum sicherstellt, dass der Baum jederzeit angemessen ausgeglichen ist.

Schneller Joe Smith
quelle
1
Persönlich finde ich Rot-Schwarz-Insert einfacher als AVL-Insert. Der Grund liegt in der (unvollkommenen) Analogie zu B-Bäumen. Einfügungen sind fummelig, aber Löschungen sind böse (so viele Fälle, die berücksichtigt werden müssen). Tatsächlich habe ich keine eigene C ++ - Rot-Schwarz-Löschimplementierung mehr - ich habe sie gelöscht, als mir klar wurde (1), dass ich sie nie verwendet habe - jedes Mal, wenn ich löschen wollte, habe ich mehrere Elemente gelöscht, also habe ich von Baum zu konvertiert liste, lösche aus der liste, konvertiere dann zurück in einen baum und (2) es war trotzdem kaputt.
Steve314
2
@ Steve314, rot-schwarze Bäume sind einfacher, aber Sie konnten keine Implementierung vornehmen, die funktioniert? Wie sind AVL-Bäume dann?
dan_waterworth
@dan_waterworth - Ich habe noch keine Implementierung mit einer Einfügemethode durchgeführt, die noch funktioniert - habe Notizen, verstehe das Grundprinzip, habe aber nie die richtige Kombination aus Motivation, Zeit und Selbstvertrauen. Wenn ich nur Versionen haben wollte, die funktionieren, dann ist das nur Kopieren-Pseudocode-aus-Lehrbuch-und-Übersetzen (und nicht vergessen, dass C ++ Standard-Bibliothekscontainer hat), aber wo ist der Spaß dabei?
Steve314
Übrigens - ich glaube (kann aber nicht die Referenz liefern), dass ein ziemlich populäres Lehrbuch eine fehlerhafte Implementierung eines der Algorithmen für ausgeglichene Binärbäume enthält - nicht sicher, aber es könnte ein rot-schwarzes Löschen sein. Also
bin
1
@ Steve314, ich weiß, Bäume können in der imperativen Sprache teuflisch kompliziert sein, aber überraschenderweise war es ein Kinderspiel, sie in Haskell zu implementieren. Ich habe über das Wochenende einen regulären AVL-Baum und auch eine räumliche 1D-Variante geschrieben, und beide sind nur etwa 60 Zeilen lang.
Dan_waterworth
10

Ich würde eine Alternative in Betracht ziehen, wenn Sie mit randomisierten Datenstrukturen zurechtkommen: Listen überspringen .

Aus einer übergeordneten Sicht handelt es sich um eine Baumstruktur, mit der Ausnahme, dass sie nicht als Baum, sondern als Liste mit mehreren Verknüpfungsebenen implementiert ist.

Sie erhalten O (log N) Einfügungen / Suchen / Löschen und müssen sich nicht mit all diesen kniffligen Fällen des Neuausgleichs befassen.

Ich habe noch nie darüber nachgedacht, sie in einer funktionalen Sprache zu implementieren, und die Wikipedia-Seite zeigt keine an, so dass es möglicherweise nicht einfach ist (wegen Unveränderlichkeit).

Matthieu M.
quelle
Ich mag es wirklich, Listen zu überspringen, und ich habe sie schon einmal implementiert, allerdings nicht in einer funktionalen Sprache. Ich denke, ich werde es danach versuchen, aber im Moment bin ich auf sich selbst ausgleichenden Bäumen.
Dan_waterworth
Außerdem verwenden die Benutzer häufig Skiplists für gleichzeitige Datenstrukturen. Anstatt die Unveränderlichkeit zu erzwingen, ist es möglicherweise besser, die Parallelitätsprimitive von haskell (wie MVar oder TVar) zu verwenden. Das bringt mir allerdings nicht viel über das Schreiben von funktionalem Code bei.
dan_waterworth
2
@ Fanatic23, eine Skip List ist kein ADT. Das ADT ist entweder eine Menge oder ein assoziatives Array.
Dan_waterworth
@ dan_waterworth my bad, du hast recht.
Fanatic23
5

Wenn Sie mit einer relativ einfachen Struktur beginnen möchten (sowohl AVL-Bäume als auch rot-schwarze Bäume sind fummelig), ist eine Option ein Treap - benannt als eine Kombination aus "Baum" und "Haufen".

Jeder Knoten erhält einen "Prioritäts" -Wert, der beim Erstellen des Knotens häufig zufällig zugewiesen wird. Knoten werden in der Baumstruktur so positioniert, dass die Schlüsselreihenfolge und die haufenartige Reihenfolge der Prioritätswerte eingehalten wird. Heap-ähnliche Reihenfolge bedeutet, dass beide Kinder eines Elternteils niedrigere Prioritäten als das Elternteil haben.

BEARBEITEN wurde "innerhalb der Schlüsselwerte" oben gelöscht - die Priorität und die Schlüsselreihenfolge gelten zusammen, sodass die Priorität auch für eindeutige Schlüssel von Bedeutung ist.

Es ist eine interessante Kombination. Wenn Schlüssel eindeutig und Prioritäten eindeutig sind, gibt es eine eindeutige Baumstruktur für jede Gruppe von Knoten. Trotzdem sind Einfügungen und Löschungen effizient. Streng genommen kann der Baum bis zu einem Punkt aus dem Gleichgewicht gebracht werden, an dem es sich tatsächlich um eine verknüpfte Liste handelt. Dies ist jedoch äußerst unwahrscheinlich (wie bei Standard-Binärbäumen), auch in normalen Fällen, wenn Schlüssel in der richtigen Reihenfolge eingefügt werden (im Gegensatz zu Standard-Binärbäumen).

Steve314
quelle
1
+1. Treaps ist meine persönliche Wahl, ich habe sogar einen Blog-Beitrag darüber geschrieben, wie sie implementiert werden.
P Shved
5

Welches ist am effizientesten?

Vage und schwer zu beantworten. Die Komplexität der Berechnungen ist klar definiert. Wenn Sie das mit Effizienz meinen, gibt es keine wirkliche Debatte. In der Tat kommen alle guten Algorithmen mit Beweisen und Komplexitätsfaktoren.

Wenn Sie "Laufzeit" oder "Speichernutzung" meinen, müssen Sie die tatsächlichen Implementierungen vergleichen. Dann spielen Sprache, Laufzeit, Betriebssystem und andere Faktoren eine Rolle, die die Beantwortung der Frage erschweren.

Welches ist am einfachsten zu implementieren?

Vage und schwer zu beantworten. Einige Algorithmen erscheinen Ihnen vielleicht komplex, aber für mich trivial.

Welches wird am häufigsten verwendet?

Vage und schwer zu beantworten. Zuerst gibt es die "von wem?" Teil davon? Nur Haskell? Was ist mit C oder C ++? Zweitens gibt es ein proprietäres Softwareproblem, bei dem wir keinen Zugriff auf die Quelle haben, um eine Umfrage durchzuführen.

Aber entscheidend, welches empfehlen Sie?

Ich nehme an, das gehört hierher, weil es offen für Diskussionen ist.

Richtig. Da Ihre anderen Kriterien nicht sehr hilfreich sind, ist dies alles, was Sie bekommen werden.

Sie können Quellcode für eine große Anzahl von Baumalgorithmen erhalten. Wenn Sie etwas lernen möchten, können Sie einfach jeden implementieren, den Sie finden können. Sammeln Sie einfach alle Algorithmen, die Sie finden, anstatt nach einer "Empfehlung" zu fragen.

Hier ist die Liste:

http://en.wikipedia.org/wiki/Self-balancing_binary_search_tree

Es sind sechs populäre definiert. Beginnen Sie mit denen.

S.Lott
quelle
3

Wenn Sie sich für Splay-Bäume interessieren, gibt es eine einfachere Version von denen, von denen ich glaube, dass sie zuerst in einem Artikel von Allen und Munroe beschrieben wurden. Es bietet nicht die gleichen Leistungsgarantien, vermeidet jedoch Komplikationen beim Umgang mit dem "Zick-Zack" -Umwuchten im Vergleich zum "Zick-Zack" -Umwuchten.

Grundsätzlich wird bei der Suche (einschließlich der Suche nach einer Einfügemarke oder einem zu löschenden Knoten) der gefundene Knoten von unten nach oben direkt zur Wurzel gedreht (z. B. wenn eine rekursive Suchfunktion beendet wird). Bei jedem Schritt wählen Sie eine einzelne Links- oder Rechtsrotation aus, je nachdem, ob das Kind, das Sie einen weiteren Schritt zur Wurzel hin hochziehen möchten, das rechte Kind oder das linke Kind war (wenn ich mich richtig an meine Rotationsrichtungen erinnere, ist das jeweils).

Wie bei Splay-Bäumen ist die Idee, dass sich zuletzt aufgerufene Objekte immer in der Nähe der Wurzel des Baums befinden und so schnell wieder zugänglich sind. Diese Allen-Munroe-Stammbäume (wie ich sie nenne - sie kennen den offiziellen Namen nicht) sind zwar einfacher, haben aber nicht die gleiche Garantie für die Leistung, die sich amortisiert.

Eine Sache - da diese Datenstruktur per Definition auch für Suchoperationen mutiert, müsste sie wahrscheinlich monadisch implementiert werden. IOW ist es vielleicht nicht gut für die funktionale Programmierung.

Steve314
quelle
Spektakel sind etwas ärgerlich, da sie den Baum auch beim Auffinden verändern. Dies wäre in Umgebungen mit mehreren Threads ziemlich schmerzhaft, was eine der großen Motivationen für die Verwendung einer funktionalen Sprache wie Haskell ist. Andererseits habe ich noch nie zuvor funktionale Sprachen verwendet. Vielleicht spielt dies also keine Rolle.
Quick Joe Smith
@Quick - hängt davon ab, wie Sie den Baum verwenden möchten. Wenn Sie es in echtem funktionalem Code verwenden würden, würden Sie entweder die Mutation bei jedem Fund löschen (was einen Splay-Baum etwas albern macht), oder Sie würden einen wesentlichen Teil des Binärbaums bei jeder Suche duplizieren. und verfolgen Sie, mit welchem ​​Baumstatus Sie arbeiten, während Ihre Arbeit fortschreitet (der Grund für die Verwendung eines monadischen Stils). Dieses Kopieren wird möglicherweise vom Compiler wegoptimiert, wenn Sie nach dem Erstellen des neuen nicht mehr auf den alten Baumstatus verweisen (ähnliche Annahmen sind bei der funktionalen Programmierung üblich), dies jedoch möglicherweise nicht.
Steve314
Kein Ansatz klingt die Mühe wert. Zum anderen meistens auch keine rein funktionalen Sprachen.
Schnell Joe Smith
1
@Quick - Duplizieren des Baums ist das, was Sie für jede Baumdatenstruktur in einer reinen Funktionssprache zum Mutieren von Algorithmen wie Einfügungen tun. In Bezug auf den Quellcode unterscheidet sich der Code nicht wesentlich von dem Code, der direkte Aktualisierungen vornimmt. Die Unterschiede haben sich vermutlich bereits für unausgeglichene Binärbäume ausgewirkt. Solange Sie nicht versuchen, übergeordnete Links zu Knoten hinzuzufügen, haben die Duplikate mindestens gemeinsame Teilbäume, und die tiefgreifende Optimierung in Haskell ist ziemlich hardcore, wenn nicht sogar perfekt. Ich bin im Prinzip selbst Anti-Haskell, aber das ist nicht unbedingt ein Problem.
Steve314
2

Ein sehr einfacher ausgeglichener Baum ist ein AA-Baum . Die Invariante ist einfacher und damit einfacher zu implementieren. Aufgrund seiner Einfachheit ist seine Leistung immer noch gut.

Als erweiterte Übung können Sie versuchen, mit GADTs eine der Varianten von ausgeglichenen Bäumen zu implementieren, deren Invariante vom Typsystemtyp erzwungen wird.

Petr Pudlák
quelle