Interval Tree

Consider a situation where we have a set of intervals and we need following operations to be implemented efficiently.
1)Add an interval
2)Remove an interval
3)Given an interval x, find if x overlaps with any of the existing intervals.

_Interval Tree:_The idea is to augment a self-balancing Binary Search Tree (BST) likeRed Black Tree,AVL Tree, etc to maintain set of intervals so that all operations can be done in O(Logn) time.

Every node of Interval Tree stores following information.
a)i: An interval which is represented as a pair[low, high]
b)max: Maximum_high_value in subtree rooted with this node.

The low value of an interval is used as key to maintain order in BST. The insert and delete operations are same as insert and delete in self-balancing BST used.

The main operation is to search for an overlapping interval. Following is algorithm for searching an overlapping intervalx_in an Interval tree rooted with_root.

Interval overlappingIntervalSearch(root, x)

1) 
If x overlaps with root's interval, return the root's interval.


2)
 If left child of root is not empty and the 
max 
 in left child 
is greater than x's low value, recur for left child


3)
 Else recur for right child.