title: IntervalTree DeleteNode Java Implementation
body: <p>I need an <a href="http://en.wikipedia.org/wiki/Interval_tree" rel="nofollow noreferrer">IntervalTree</a> or RangeTree implementation in Java, and am having trouble finding one with working deletion support.</p>
  
  <p>There's a built-in one at <a href="http://www.docjar.org/html/api/sun/jvm/hotspot/utilities/IntervalTree.java.html" rel="nofollow noreferrer">sun.jvm.hotspot.utilities.IntervalTree</a>, but the <a href="http://www.docjar.org/html/api/sun/jvm/hotspot/utilities/RBTree.java.html#171" rel="nofollow noreferrer">deleteNode</a> method in the RBTree superclass states:</p>
  
  <pre><code>/**
   * 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.
   */
  </code></pre>
  
  <p>Trying to delete nodes from a tree ends up throwing the exception:</p>
  
  <blockquote>
    <p>Node's max endpoint was not updated
    properly</p>
  </blockquote>
  
  <p>How difficult would it be to properly implement <code>delete</code> functionality in a subclass of the sun.jvm.hotspot.utilities.IntervalTree?  Or is there another Interval Tree implementation which already implements this correctly?  </p>
  
  <p>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).</p>