Ich brauche eineIntervalTree oder RangeTree-Implementierung in Java, und ich habe Probleme, eine mit funktionierender Löschunterstützung zu finden.

Es gibt eine eingebaute beisun.jvm.hotspot.utilities.IntervalTree, aber dieKnoten löschen Methode in der RBTree-Oberklasse lautet:

/**
 * 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.
 */

Beim Versuch, Knoten aus einem Baum zu löschen, wird die folgende Ausnahme ausgelöst:

Der maximale Endpunkt des Knotens wurde nicht ordnungsgemäß aktualisiert

Wie schwierig wäre es, dies richtig umzusetzendelete Funktionalität in einer Unterklasse von sun.jvm.hotspot.utilities.IntervalTree? Oder gibt es eine andere Implementierung von Interval Tree, die dies bereits korrekt implementiert?

Momentan lösche ich den Baum nur aus und fülle ihn jedes Mal neu auf, wenn es eine Löschung gibt, was alles andere als ideal ist (Anmerkung: DEBUGGING = false im RBTree beschleunigt die Dinge enorm).