title: Augment java collection to get Interval Tree
body: <p>I was going through the <a href="https://rads.stackoverflow.com/amzn/click/com/0262033844" rel="nofollow noreferrer" rel="nofollow noreferrer">Introduction to Algorithms by Cormen</a> chapter 14 (augmented data structures), in which he was talking about Interval Trees. Below is what he mentioned about the design approach behind interval tree.</p>
  <blockquote>
  <p><strong>Step 1: Underlying data structure</strong></p>
  <p>We choose a red-black tree in which each node <em>x</em> contains an interval <em>x:int</em> and the key of <em>x</em> is the low endpoint, <em>x.int.low</em>, of the interval. Thus, an inorder tree walk of the data structure lists the intervals in sorted order by low endpoint.</p>
  </blockquote>
  <p>This can be done by declaring a node having <em>min</em> and <em>max</em>. The <em>comparableTo</em> function should compare only <em>x.int.low</em>.</p>
  <blockquote>
  <p><strong>Step 2: Additional information</strong></p>
  <p>In addition to the intervals themselves, each node <em>x</em> contains a value <em>x.max</em>, which is the maximum value of any interval endpoint stored in the sub-tree rooted at <em>x</em>.</p>
  <p><strong>Step 3: Maintaining the information</strong></p>
  <p>We must verify that insertion and deletion take <em>O(lg n)</em> time on an interval tree of n nodes. We can determine <em>x.max</em> given interval <em>x.int</em> and the <em>max</em> values of node <em>x</em>’s children:</p>
  <p><em>x:max = max(x.int.high; x.left.max; x.right.max)</em></p>
  <p><strong>Step 4: Developing new operations</strong></p>
  <p>The only new operation we need is <code>INTERVAL-SEARCH</code>(<em>T</em>,<em>i</em>), which finds a node in tree <em>T</em> whose interval overlaps interval <em>i</em>. If there is no interval that overlaps <em>i</em> in the tree, the procedure returns a pointer to the sentinel <em>T:nil</em>.</p>
  </blockquote>
  <p>I can implement this by <em>AVL tree</em> but out of curiosity want to know whether we can augment existing libraries in java like <em>TreeSet</em> or other <em>collection entity</em> to fit to above design. If so, can you please help in a sample code or example?</p>