Ich erinnere mich, dass ich eine Datenstruktur gelernt habe, die ganze Zahlen als Bereiche in einem Baum gespeichert hat, aber es sind 10 Jahre vergangen und ich kann mich nicht mehr an den Namen der Datenstruktur erinnern, und ich bin ein wenig verschwommen. Wenn es hilft, ist es eine funktionale Datenstruktur, die an der CMU gelehrt wurde, glaube ich an 15-212 (Principles of Programming) im Jahr 2002.
Grundsätzlich möchte ich eine Menge von Ganzzahlen speichern, von denen die meisten aufeinanderfolgend sind. Ich möchte in der Lage sein, die Mengenzugehörigkeit effizient abzufragen, einen Bereich von Ganzzahlen effizient hinzuzufügen und einen Bereich von Ganzzahlen effizient zu entfernen. Insbesondere achte ich nicht darauf, die ursprünglichen Bereiche zu erhalten. Es ist besser, wenn benachbarte Bereiche zu einem einzigen größeren Bereich verschmolzen werden.
Eine naive Implementierung wäre, einfach eine generische Set-Datenstruktur wie HashSet oder TreeSet zu verwenden und beim Hinzufügen eines Bereichs alle Ganzzahlen in einem Bereich hinzuzufügen oder beim Entfernen eines Bereichs alle Ganzzahlen in einem Bereich zu entfernen. Aber natürlich würde das eine Menge Speicher verschwenden, zusätzlich dazu, Add und Remove langsam zu machen.
Ich denke an eine rein funktionale Datenstruktur, aber für meine aktuelle Verwendung brauche ich sie nicht. IIRC, Nachschlagen, Einfügen und Löschen waren alle O (log N), wobei N die Anzahl der Bereiche in der Menge war.
Können Sie mir also den Namen der Datenstruktur nennen, an die ich mich zu erinnern versuche, oder eine geeignete Alternative?
Ich fand die alten Hausaufgaben und die Datenstruktur, die ich im Sinn hatte, waren Discrete Interval Encoding Trees oder Diäten kurz. Sie werden detailliert in Diäten für Fat Sets , Martin Erwig, beschrieben. Zeitschrift für Funktionale Programmierung, Vol. 8, Nr. 6, 627-632, 1998. Es ist im Grunde ein Baum von Intervallen mit der Invariante, dass alle Intervalle nicht überlappend und nicht berührend sind. Es gibt eine Haskell-Implementierung in Hackage . Ich hatte gehofft, dass es eine existierende Implementierung für Scala geben würde, aber ich sehe keine.
Die Hausaufgaben enthielten auch eine andere Datenstruktur, die sie einen rekursiven Interval-Okkludierenden Baum (RIOT) nannten, der anstatt nur ein Intervall an jedem Knoten zu halten ein Intervall und einen anderen (möglicherweise leeren) RIOT von Dingen aus dem Intervall entfernt. Die Aufgabe umfasste Benchmarks, die zeigten, dass es besser war als Diäten für zufällige Insertionen und Deletionen. AFAICT es ist einfach etwas, das die TAs erfunden und nie veröffentlicht haben, da es nirgends mehr im Internet zu existieren scheint, zumindest nicht unter diesem Namen.
Sie suchen wahrscheinlich nach Segmentbäumen. Dies könnte hilfreich sein: Ссылка
Sie können auch binäre Suchbäume für dieselben verwenden, für die jeder Knoten zwei Datenfelder hat: min_val und max_val.
Während des Einfügealgorithmus müssen Sie nur eine weitere Zusammenführungsoperation aufrufen, um zu überprüfen, ob das linke Kind, das übergeordnete Element oder das rechte Kind eine Sequenz erstellen, um sie in einen einzigen Knoten zu vereinigen. Dies dauert O (log n) Zeit.
Andere Operationen wie Löschen und Nachschlagen benötigen O (log n) wie gewohnt, aber beim Löschen müssen besondere Maßnahmen getroffen werden.
Tags und Links data-structures functional-programming