I need an IntervalTree or RangeTree implementation in Java, and am having trouble finding one with working deletion support.
There's a built-in one at sun.jvm.hotspot.utilities.IntervalTree, but the deleteNode method in the RBTree superclass states:
/**
* 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.
*/
Trying to delete nodes from a tree ends up throwing the exception:
Node's max endpoint was not updated properly
How difficult would it be to properly implement delete functionality in a subclass of the sun.jvm.hotspot.utilities.IntervalTree? Or is there another Interval Tree implementation which already implements this correctly?
Currently I'm just wiping out the tree and re-populating it every time there's a deletion, which is far from ideal (note: setting DEBUGGING=false in the RBTree sped things up tremendously).
I ended up modifying the sun.jvm.hotspot.utilities.IntervalTree to maintain a Set of deleted nodes. When doing a search, I exclude any items in this set. Not ideal, but this was a lot easier than getting "real" deletion working. Once the deleted set gets too large, I rebuild the tree.