Bäume mit den Werten auf den Blättern nur

Question

Vor ein paar Jahren, während eines C# Kurs lernte ich einen binären Baum zu schreiben, die mehr oder weniger so aussah:

data Tree a = Branch a (Tree a) (Tree a) | Leaf 

ich den Vorteil der es sah, hatte sie seine Werte auf den Zweigen, die ein schnelles und einfaches Nachschlagen und Einfügen von Werten ermöglichten, weil es einen Wert auf der Wurzel jedes Zweigs bis hinunter zu einem Blatt treffen würde, das keinen Wert enthielt.

Seit ich Haskell zu lernen begann, jedoch; Ich habe zahlreiche Beispiele von Bäumen gesehen, die wie folgt definiert sind:

data Tree a = Branch (Tree a) (Tree a) | Leaf a 

Diese Definition verwirrt mich. Ich kann nicht den Nutzen, die Daten über die Elemente sehen, dass nicht Zweig tun, weil es an einem Baum enden würde, führt, die wie folgt aussieht:

Was mir scheint wie eine schlecht gestaltete Alternative zu einer Liste. Es lässt mich auch die Nachschlagzeit in Frage stellen, da es nicht beurteilen kann, welcher Zweig nach unten geht, um den Wert zu finden, nach dem er sucht; sondern muss jeden Knoten durchlaufen, um zu finden, wonach er sucht.

Also, kann jemand etwas Licht darauf werfen, warum die zweite Version (Wert auf Blättern) ist so viel häufiger in Haskell als die erste Version?

Answer 1

Ich denke, das hängt davon ab, was Sie versuchen zu modellieren und wie Sie versuchen, es zu modellieren.

Ein Baum, in dem die internen Knoten Werte speichern und die Blätter nur Blätter sind, ist im Wesentlichen ein Standard-Binärbaum (Baum jedes Blatt als NULL und Sie haben im Grunde einen binären Baum im imperativ-Stil). Wenn die Werte in sortierter Reihenfolge gespeichert werden, haben Sie jetzt einen binären Suchbaum. Es gibt viele spezifische Vorteile beim Speichern von Daten auf diese Weise, von denen die meisten direkt von imperativen Einstellungen übertragen werden.

Bäume, in denen die Blätter die Daten speichern und die internen Knoten nur für die Struktur sind, haben ihre Vorteile. Zum Beispiel unterstützen Rot/Schwarz-Bäume zwei mächtige Operationen, die split und join genannt werden, die in einigen Umständen Vorteile haben. split nimmt als Eingabe einen Schlüssel, ändert dann den Baum zerstörend, um zwei Bäume zu erzeugen, von denen einer alle Schlüssel weniger als den spezifizierten Eingabeschlüssel und einen Schlüssel die restlichen Schlüssel enthält. join ist in gewissem Sinne das Gegenteil: Es nimmt zwei Bäume auf, in denen die Werte eines Baumes alle kleiner sind als die Werte des anderen Baums, und fusioniert sie dann zu einem einzigen Baum. Diese Operationen sind bei den meisten Rot/Schwarz-Bäumen besonders schwierig zu implementieren, sind jedoch viel einfacher, wenn alle Daten nur in den Blättern und nicht in den internen Knoten gespeichert werden. This paper detailing an imperative implementation of red/black trees erwähnt, dass einige ältere Implementierungen von Rot/Schwarz-Bäumen diesen Ansatz aus diesem Grund verwendeten.

Als weiteren möglichen Vorteil des Speicherns von Schlüsseln in den Blättern sollten Sie die Verkettungsoperation implementieren, die zwei Listen miteinander verbindet. Wenn Sie keine Daten in den Blättern haben, ist dies so einfach wie

concat first second = Branch first second 

Dies funktioniert, weil keine Daten in diesem Knoten gespeichert sind. Wenn die Daten in den Blättern gespeichert sind, müssen Sie einen Schlüssel von einem der Blätter in den neuen Verkettungsknoten verschieben, was mehr Zeit in Anspruch nimmt und schwieriger zu verarbeiten ist.

Schließlich möchten Sie in einigen Fällen die Daten in den Blättern speichern, da sich die Blätter grundlegend von internen Knoten unterscheiden. Betrachten Sie zum Beispiel einen Syntaxbaum, in dem die Blätter bestimmte Terminals aus der Analyse speichern und die internen Knoten alle Nichtterminale in der Produktion speichern. In diesem Fall gibt es wirklich zwei verschiedene Arten von Knoten, so dass es nicht sinnvoll ist, beliebige Daten in den internen Knoten zu speichern.

Hoffe, das hilft!

Answer 2

Mehr ist besser schlechter mehr. Ich werde nur ein paar grundlegende Überlegungen erklären, warum Ihre Intuition scheitert. Die allgemeine Idee ist jedoch, dass unterschiedliche Datenstrukturen unterschiedliche Dinge benötigen.

Leere Blattknoten können in einigen Kontexten tatsächlich ein Leerzeichen (und daher Zeit) sein. Wenn ein Knoten durch ein bisschen Information und zwei Zeiger auf seine Kinder dargestellt wird, erhalten Sie zwei Nullzeiger pro Knoten, deren Kinder beide Blätter sind. Das sind zwei Maschinenwörter pro Blattknoten, die ziemlich viel Platz ergeben können. Einige Strukturen vermeiden dies, indem sie sicherstellen, dass jedes Blatt mindestens eine Information enthält, um seine Existenz zu rechtfertigen. In einigen Fällen (wie ropes) kann jedes Blatt eine ziemlich große und dichte Nutzlast haben.

Wenn Sie interne Knoten vergrößern (indem Sie Informationen in ihnen speichern), wird es teurer, den Baum zu ändern. Wenn Sie ein Blatt in einem ausgeglichenen Baum ändern, müssen Sie normalerweise Ersatz für interne Knoten O(log n) zuweisen. Wenn jeder dieser Bereiche größer ist, haben Sie einfach mehr Platz zugewiesen und zusätzliche Zeit aufgewendet, um weitere Wörter zu kopieren. Die zusätzliche Größe der internen Knoten bedeutet auch, dass Sie weniger Struktur Struktur in den CPU-Cache passen können.

Answer 3

Sie haben einen Baum mit Daten an den Blättern als "schlecht entworfene Alternative zu einer Liste" beschrieben.

Ich stimme zu, dass dies als eine Alternative zu einer Liste verwendet werden könnte, aber es ist nicht unbedingt schlecht designed! Betrachten Sie den Datentyp

data Tree t = Leaf t | Branch (Tree t) (Tree t) 

Sie können festlegen, cons und snoc (Anfügen von Liste zu beenden) Operationen -

cons :: t -> Tree t -> Tree t 
cons t (Leaf s)  = Branch (Leaf t) (Leaf s) 
cons t (Branch l r) = Branch (cons t l) r 

snoc :: Tree t -> t -> Tree t 
snoc (Leaf s)  t = Branch (Leaf s) (Leaf t) 
snoc (Branch l r) t = Branch l (snoc r t) 

Diese Lauf (für etwa ausgeglichen Listen) in O (log n) Zeit, in der n ist die Länge der Liste. Dies steht im Gegensatz zu der Standardverknüpfungsliste, die O (1) cons und O (n) snoc Operationen aufweist. Sie können auch eine konstante Zeit append (wie in templatetypedef Antwort)

append :: Tree t -> Tree t -> Tree t 
append l r = Branch l r 

definieren, die O (1) für zwei Listen von beliebiger Größe, während die Standard-Liste ist O (n), wobei n die Länge der das linke Argument.

In der Praxis möchten Sie etwas intelligentere Versionen dieser Funktionen definieren, die versuchen, den Baum im Gleichgewicht zu halten.Um dies zu tun, ist es oft nützlich, einige zusätzliche Informationen in den Zweigen zu haben, was durch mehrere Arten von Verzweigungen (wie in einem Rot-Schwarz-Baum, der "rote" und "schwarze" Knoten hat) geschehen kann oder explizit zusätzliche Daten einschließt an den Zweigen, wie in

data Tree b a = Leaf a | Branch b (Tree b a) (Tree b a) 

Zum Beispiel können Sie einen O (1) size Operation durch die Gesamtzahl der Elemente in den beiden Speichern von Unterstrukturen in den Knoten unterstützen. Alle Ihre Operationen auf dem Baum werden ein wenig komplizierter, da Sie die Informationen über Teilbaumgrößen korrekt beibehalten müssen - in der Tat amortisiert sich die Arbeit der Berechnung der Baumgröße über alle Operationen, die den Baum aufbauen (und clever beibehalten, so dass nur minimale Arbeit geleistet wird, wenn Sie später eine Größe rekonstruieren müssen).