Gibt es eine Implementierung eines binären Suchbaums, der mit Unterbaumgröße kommentiert ist?

Question

Ich habe die in diesem Link beschriebene Baumdatenstruktur untersucht (nahe am Boden):

http://sigpipe.macromates.com/2009/08/13/maintaining-a--Layout/

Es wird erwähnt, dass diese Datenstruktur ein Fingerbaum sein könnte. Nach mehr Nachforschungen um Fingerbäume habe ich jedoch festgestellt, dass dies nicht die "Finger", die Fingerbäume Fingerbäume machen. Stattdessen scheint dies nur ein kommentierter binärer Baum (mit Subtree -Größe kommentiert).

Kennen Sie eine vorhandene Implementierung (in jeder Sprache) dieser Datenstruktur, die ich als Referenz für meine eigene Implementierung verwenden könnte (vorzugsweise vorzugsweise nicht eine Implementierung in einer funktionalen Programmiersprache)?

Oder wie wäre es der optimalste Weg, die Annotationen der Subtree-Größe in eine vorhandene Baumdatenstruktur nachzurüsten?

Vielen Dank!

Answer 1

Simon Tathams gezählte B-Bäume sind ähnlich. Wenn die Knotenzahl durch eine Pufferbreite ersetzt wird wie in optimieren, Diese bieten Operationen wie Seile.

In der Tat aus dem Lesen der Seite, auf die Sie verweisen, sehe ich, dass sie wie eine Stücktabelle oder eine Zeilentabelle für einen Editor verwendet wurde

in der Zeitung, Positionsdelta-Bäume, um Updates mit readoptimierten Datenspeicherung in Einklang zu bringen, die Autoren präsentieren einen Baum, der in Bezug auf die Invarianten, die sie zwischen den Knoten im Baum halten Xanadus Enfiladen Zu denen ist auch der gezählte B-Baum ähnlich.

Answer 2

Ich habe ein Projekt auf Github namens Boost.Intusive kommentierte Bäume Dies zielt darauf ab, allgemeine Unterstützung für Anmerkungen wie die Anzahl der Subtree in Boost.inTusive zu leisten. Die Anzahl der Subtree war mein ursprünglicher Anwendungsfall dafür.

Derzeit sind C ++ 11 Variadic -Vorlagen erforderlich und unterstützt nur die RBTree, aber es funktioniert, und ich hoffe, beide Einschränkungen zeitlich zu entfernen Aktualisieren: Jetzt baut mit C ++ 03. Immer noch unterstützt rbtree.

Wenn sie mit einer Annotation mit Subtree -Anzahl verwendet wird, ähnelt sie dem, was Jordan in der obigen Antwort beschreibt - sie berechnet an jedem Knoten (links+rechts+1). Die Implementierung ist ganz anders - sie funktioniert mit jedem Knoten und/oder Wertschöpfungsmerkmalen; Die Annotations -Updates sind stattdessen in die RBTree -Algorithmen integriert, wodurch die Anzahl der Rekulkulationen minimal durchgeführt wird.

Answer 3

Ich habe etwas Ähnliches implementiert, basierend auf einer Frage, die ich neulich gestellt habe. Ich habe den Boost :: Intrusiv :: rbtree/avltree-Knoten Anmerkungen hinzugefügt, um die Größe jedes Teilbaums zu berechnen (foreach node count = node-> links-> count + node-> rechts-> count + 1). Ich führe dieses Update über Insertion/Deletetion/Wiederausgleich des Baumes durch, indem ich den Boost Value_traits -Hook für set_parent, set_left und set_right verwende. Aktualisieren Sie, wie auf der Website, auf die Sie sich bezogen haben, nach jedem Knoten -Update die Größe des aktuellen Knotens und durchqueren Sie den Baum, bis Sie das Root drücken, und aktualisieren Sie die Größe jedes Knotens, während Sie gehen.

Das Problem kommt, wenn Sie an einer bestimmten Position in den Baum einfügen möchten. In dem Moment, in dem Sie dies tun, werden Sie die Schlüsselbestellung für die Baumstruktur ungültig machen. Dies bedeutet, dass Sie nicht in der Lage sind, effiziente O (log n) -Scookups nach Schlüssel durchzuführen. Aber wenn Sie das wollten, würden Sie wahrscheinlich die Größenanmerkungen sowieso nicht benötigen.