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