Interval Tree

Operation supported:

• Add an interval

• Remove an interval

• Given an X, find it overlaps with any existing interval.

The low value of an interval is used as a key to maintain order of BST.

class TreeNode {
    Interval interval;
    TreeNode left;
    TreeNode right;
    int endMax;  //maximum high value of the intervals in the subtree rooted by the current node.
}

eg. [5,20] [10,30] [12,15] [15,20] [17,19] [30,40] (overlapping range).

                         [12,15],40

                 /                        \

            [5,8],30                       [17,19],40

                     \                    /             \

                   [10,30],30         [15,20],20      [30,40],40

find any interval covering target point from the root.

How to prove?

refer CLRS.

• identify two interval relationship

  • intersected <a,b> -> a.low < b.hi && b.lo <= a.hi

  • a is at left of b -> a.hi < b.lo

  • a is to right of b -> b.hi < a.lo

• algorithm Search(TreeNode root， Interval target) ;

  • target overlap root.interval, we are done.
  • root.left != null && if target.low <= root.left.max
  • else search to right.

• Why this work ? How to prove?

  画图解释CLRS. p352 chap14.

  • proof case 1: if search right, target.lo > left. max right boundary in tree
  • ```

               |
               | -------(target)
_______________|____________________
            x.left.max

easy to prove all in left subtree can't overlap with target interval.

• case 2: if search left, target.lo <= left.max

  • case2.1 find one, we are done.
  • case 2.2 can't find one in left subtree, at this time, lower bound is leftMost.

                           --------
                   --------------    
|__i__|  |-----i''----|
----------------------|------------------------>
                   left.max

if it doesn't overlap i'', it will not overlap with any interval in right subtree.