IntervalTree DeleteNode Java Implementation

Question

Ich brauche eine IntervalTree oder Bereichsbaum Implementierung in Java und Mühe habe einen zu finden, mit der Streichung Unterstützung arbeiten.

Es gibt eine eingebaute in einem an sun.jvm.hotspot.utilities.IntervalTree, aber die deleteNode Methode in den RBTree Super heißt es:

/** 
* FIXME: this does not work properly yet for augmented red-black 
* trees since it doesn't update nodes. Need to figure out exactly 
* from which points we need to propagate updates upwards. 
*/ 

Der Versuch, Knoten zu löschen von einem Baum, um die Ausnahme zu werfen endet:

Knotens max Endpunkt wurde nicht aktualisiert richtig

Wie schwierig wäre es zu pr implementieren Sie delete Funktionalität in einer Unterklasse der sun.jvm.hotspot.utilities.IntervalTree? Oder gibt es eine andere Interval Tree-Implementierung, die dies bereits korrekt implementiert?

Zur Zeit bin ich nur den Baum auszulöschen und wieder bevölkern es jedes Mal, wenn es eine Deletion, die bei weitem nicht ideal ist (Anmerkung: Einstellung DEBUGGEN = false in der RBTree Dinge beschleunigt enorm).

Answer 1

endete ich die sun.jvm.hotspot.utilities.IntervalTree Modifikation auf einen Satz von gelöschten Knoten zu halten. Bei einer Suche schließe ich alle Elemente in diesem Set aus. Nicht ideal, aber das war viel einfacher als das "echte" Löschen funktioniert. Sobald der gelöschte Satz zu groß wird, baue ich den Baum neu auf.

Answer 2

This project hat eine Implementierung Bereichsbaum, die für Sie von größerem Nutzen sein könnte. Die Sonnenpakete könnten für eine schnelle und dreckige Nutzung in Ordnung sein, aber ich würde nicht empfehlen, etwas Wichtiges aufzubauen, wenn man sich darauf verlässt. Sun kann sie nicht stabil halten.

Answer 3

Ich kenne Ihre genauen Anforderungen nicht, aber ein nicht statischer Segmentbaum könnte für Sie arbeiten. Wenn ja, werfen Sie einen Blick auf Layout Management SW, speziell die SegmentTree package. Es hat die Remove-Funktion, die Sie benötigen.

Wenn Sie sich entscheiden, Ihre eigenen zu rollen, kann ich vorschlagen, Open Sourcing es? Ich bin überrascht, dass es noch keinen offenen und einfachen Interval Tree gibt.

Answer 4

gibt es eine C# Implementierung basiert auf einem Augmented AVL-Baum @http://code.google.com/p/intervaltree/. Übersetzung in Java sollte nicht zu schwierig sein.

Answer 5

Ich habe eine Open-Source-Implementierung mit Löschung gefunden, aber es bedarf einiger Anstrengungen, um sie voll funktionsfähig zu machen.

Es ist ein Modul des größeren Open-Source-Projekts Gephi, aber hier sind die sources und javadoc. Wenn Sie ein Glas möchten, können Sie die Gephi installieren, und es ist in:

/gephi/modules/org-gephi-data-attributes-api.jar 

Die Löschmethode gibt, werden alle Intervalle mit dem Eingangsintervall überlappen (statt nur den Eingang eins). Jedoch habe ich in den Quellen gefunden, dass es private Methoden gibt, die einen bestimmten Knoten entfernen (der ein Intervall speichert). Auch die privaten Suchmethoden geben Knoten zurück.

Also ich denke, mit etwas wenig Aufwand ist es möglich, den Code und haben diese Refactoring - Feature ‚bestimmten Intervall löschen‘. Der schnellste und schmutzigste Weg wäre, die privaten Methoden/Node-Klasse öffentlich zu machen. Aber da es sich um ein Open-Source-Projekt handelt, könnte es sich vielleicht in Zukunft zu einer guten Standardimplementierung des Intervallbaums entwickeln.