**Problem**

Discuss Interval Search Tree

**Idea behind Interval Search Tree**

Lets discuss the 1D Interval search. By 1D I mean in 1 dimension i.e. having interval along 1 axis only. So, suppose along x axis we have collection of intervals - [1,2], [1,3] and so on.

Here Interval Tree or Interval Search tree is helpful as it holds set of (overlapping) intervals

- Insert the interval
- Search
- delete
- Main functionality - Interval intersection query - given the interval (lo, hi) find all intervals in data structure which intersect with given interval.

**Data structure for IST**

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

**Interval Tree:**Every node of Interval Tree stores following information.

**i**: An interval which is represented as a pair*[low, high]***max**: Maximum*high*value in subtree rooted with this node.

Here is the java data structure for Node :

private class Node { Interval1D interval; // key Value value; // associated data Node left, right; // left and right subtrees int N; // size of subtree rooted at this node int max; // max endpoint in subtree rooted at this node Node(Interval1D interval, Value value) { this.interval = interval; this.value = value; this.N = 1; this.max = interval.high; } }

Here is how the basic structure of interval search tree looks:

public class Interval1D implements Comparable<Interval1D> { public final int low; // left endpoint public final int high; // right endpoint }

The main operation is to search for an overlapping interval. Following is algorithm for searching an overlapping interval

*x*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 themaxin left child is greater than x's low value, recur for left child 3) Else recur for right child.

**Example**

Consider x = [6,7]. We see if x overlaps with root [15,20]. Answer is no. Now we check if max of left child i.e. 30 greater than x's low value i.e. 6. If yes, we move to left node. Likewise we continue, and find out interval in the tree is [5,20].

**How does the above algorithm work?**Let the interval to be searched be x. We need to prove this in for following two cases.

**Case 1:***When we go to right subtree, one of the following must be true.*

a) There is an overlap in right subtree: This is fine as we need to return one overlapping interval.

b) There is no overlap in either subtree: We go to right subtree only when either left is NULL or maximum value in left is smaller than

*x.low*. So the interval cannot be present in left subtree.

**Case 2:***When we go to left subtree, one of the following must be true.*

a) There is an overlap in left subtree: This is fine as we need to return one overlapping interval.

b) There is no overlap in either subtree: This is the most important part. We need to consider following facts.

… We went to left subtree because

*x.low <= max*in left subtree

…. max in left subtree is a high of one of the intervals let us say

*[a, max]*in left subtree.

…. Since

*x*doesn’t overlap with any node in left subtree

*x.low*must be smaller than ‘

*a*‘.

…. All nodes in BST are ordered by low value, so all nodes in right subtree must have low value greater than ‘

*a*‘.

…. From above two facts, we can say all intervals in right subtree have low value greater than

*x.low*. So

*x*cannot overlap with any interval in right subtree.

**Implementation of Interval Tree**

The code here will be too long. I have put this class in github. You may refer to Interval1D class here.

Please feel free to comment if you have any suggestions.

**Applications of Interval Tree:**

Interval tree is mainly a geometric data structure and often used for windowing queries, for instance, to find all roads on a computerized map inside a rectangular viewport, or to find all visible elements inside a three-dimensional scene (Source Wiki).

**Interval Tree vs Segment Tree**

Both segment and interval trees store intervals. Segment tree is mainly optimized for queries for a given point, and interval trees are mainly optimized for overlapping queries for a given interval. More

**here**.

**References**

http://en.wikipedia.org/wiki/Interval_tree

http://algs4.cs.princeton.edu/92search/

http://algs4.cs.princeton.edu/93intersection/IntervalST.java.html

http://algs4.cs.princeton.edu/93intersection/

http://www.geeksforgeeks.org/interval-tree/

Introduction to Algorithms 3rd Edition by Clifford Stein, Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest

https://www.youtube.com/watch?v=dQF0zyaym8A

## 0 comments:

## Post a Comment