https://www.coursera.org/learn/algorithms-part1/lecture/ot9vw/interval-search-trees
https://www.coursera.org/learn/algorithms-part1/lecture/mNiwq/rectangle-intersection
http://shirleyisnotageek.blogspot.com/2015/02/interval-search-tree.html
1. Add an interval;
2. Remove an interval;
3. Given an interval, search if it overlaps with any intervals in the list and return all those intervals.
The interval search tree follows a binary search tree structure. Each node of the tree stores the following information:
1. interval: the interval;
2. label: a unique label;
3. max: the high value of all intervals in the subtree of the current node is smaller than this one.
The compare method of the interval follows to following rule:
http://mooc.guokr.com/note/8586/
Range Search
An Interval Tree is an ordered data structure whose nodes represent the intervals and are therefore characterized by a start value and an end value. A typical application example is when we have a number of available intervals and another set of query intervals, for which we want to verify the overlap with the given intervals.
The following picture shows an example where in blue are represented a series of intervals and in yellow are defined two query intervals for which we want to verify the overlap with the previous ones:
Picture 1:
The Interval Tree structure comes into play to provide a more efficient solution than the naive approach of applying a brutal force strategy and compare each query range with all the others and check if, according to the values of the relative bounds, there is an overlap (total or partial) between them.
In making the search for nodes within the Augmented Interval Tree we will use the information we have added, relative to the maximum value of the upper bound found in the subtree of each node, to maximize the search performance and exclude unnecessary comparisons. The way we use it is the following: if the maximum value of the subtree of the left child of a node is lower than the starting point of the query range, then we can exclude from the comparison all the nodes in the entire subtree and go directly to the right subtree of the node.
http://turing.plymouth.edu/~zshen/Webfiles/notes/CS322/CodeSample/com/mhhe/clrs2e/IntervalTree.java
Interval Tree - GeeksforGeeks
Interval tree is sorted by left point.
If search goest to right, then there is no intersection in left.
Because in this case, either left tree is empty or max of left tree is lesser than(<) low, so no intersect in left tree.
If search goes to left, then there is either an intersection in left, or no intersection in either.
In latter case, because there is no intersection in left,
and say the interval with max value is [c-max],
then x.high must be lesser than c, otherwise x would be intersected with [c-max].
So x.high must be lesser than all left values in right trees, so no intersection with right tree.
http://www.drdobbs.com/cpp/interval-trees/184401179
http://www.dgp.toronto.edu/people/JamesStewart/378notes/22intervals/
Read full article from Interval Tree - GeeksforGeeks
https://www.coursera.org/learn/algorithms-part1/lecture/mNiwq/rectangle-intersection
http://shirleyisnotageek.blogspot.com/2015/02/interval-search-tree.html
1. Add an interval;
2. Remove an interval;
3. Given an interval, search if it overlaps with any intervals in the list and return all those intervals.
The interval search tree follows a binary search tree structure. Each node of the tree stores the following information:
1. interval: the interval;
2. label: a unique label;
3. max: the high value of all intervals in the subtree of the current node is smaller than this one.
The compare method of the interval follows to following rule:
1. The interval with the lower low value is always smaller
2. If the low is the same, the interval with the lower high is smaller
public Interval search(Interval interval) { return search(root, interval); } public Interval search(Node node, Interval interval) { while (node != null) { if (interval.intersects(node.interval)) return node.interval; else if (node.left == null) node = node.right; else if (node.left.max < interval.low) node = node.right; else node = node.left; } return null; } /** * return all intervals that intersect the given interval * running time is proportional to RlogN, where R * is the number of intersections * @param interval * @return */ public Iterable<interval> searchAll (Interval interval) { LinkedList<interval> list = new LinkedList<interval> (); searchAll(root, interval, list); return list; } public boolean searchAll(Node node, Interval interval, LinkedList<interval> list) { boolean found_root = false; boolean found_left = false; boolean found_right = false; if (node == null) return false; if (interval.intersects(node.interval)) { list.add(node.interval); found_root = true; } if (node.left != null && node.left.max >= interval.low) found_left = searchAll(node.left, interval, list); if (node.right != null && node.right.max >= interval.high)// found_right = searchAll(node.right, interval, list); return found_root || found_left || found_right; }Range Search
一维情况
- 查找位于两个键k1和k2之间的值
- 未排序的数组：插入很快O(1)，查找很慢O(N)
- 排序数组：插入很慢O(N)，查找很快O(1)
- binary search tree：两项都能达到O(log N)；如果在每个节点上加上序号，一维的range count可以做到O(1)，range search可以通过限定范围并递归的方式实现
- 如何在一些竖直和水平的线段里找到那些相交的？
- 像扫地毯一样从一个维度扫过去，记录其正交维度方向那些线段的在这个维度的起点和终点，当某个水平线段起始却未终止时，扫到了一条竖直线段，查询一下水平线段的高度是否在竖直线段的范围内，是的话说明这两条线段垂直相交
- 数据结构实现：用BST保存水平线段，扫到其起点时插入，扫到终点时删除；扫到垂直线段时针对垂直线段的两端对BST进行范围查找即可
- 也就是高维度树，键值是对应的k维的
- 比如二维树可以执行相应维度的空间的范围搜索（比如二维空间里搜索一个矩形内的数据）
- 具体实现：（以二维为例，）将数据所在的矩形分为一样大小的格子分每个格子存储相应的点，格子大小经验：以N的平方根划分比较好（N为数据量）
- 对于离散数据效果很好，但实际中经常出现数据的聚集，针对这个问题，可以采取递归的方式，每插入一个数据，就以它为界把当前所在的区块分成左右两部分，后面再有数据插入进这两部分就成为它的左右子节点（递归中横竖切分交替进行）（形成的图形好像艺术中的极少主义）
- search：给出一个矩形或一个点，可以从根节点开始，照着插入时候形成的左右（上下）部分递归地查找属于矩形中的点
- 群集的鸟：一定要点开看一下这个美妙的现象，那是小时候看动物世界还是什么给我留下深刻印象的美丽；它跟课程的关系没有多讲，似乎是用2-d tree可以来模拟鸟儿群聚的动态？
- N体问题：利用k-d tree来模拟
- 数据不再是一个数，而是一个区间，插入时类似BST，采取区间左端点作为排序的key
- interval search：给出一个区间，查找树中那些与它相交的区间：每个节点处记录其子树里最右端的值
- 类似地有高维情况的树
1-D range searching. Goal: answer range searches in time O(log n + k), where k is the number of matching points, and range counts in time O(log n). Output-sensitive. Can achieve by sorting the points and using binary search. This method doesn't generalize to higher dimensions since we can't define a meaningful order for two dimensional points. Also, it does not dynamically support insertions and deletions.
Create a (balanced) binary search tree, where the elements correspond to points in the set. Program RangeSearch.javaimplements this strategy using a randomized BST. (Should we simply as in 74intersection/RangeSearch.java to assume no value associated with key.) We will use this data structure to implement h-v line segment intersection in Section X.Y.
http://www.davismol.net/2016/02/07/data-structures-augmented-interval-tree-to-search-for-interval-overlapping/
The following picture shows an example where in blue are represented a series of intervals and in yellow are defined two query intervals for which we want to verify the overlap with the previous ones:
Picture 1:
The Interval Tree structure comes into play to provide a more efficient solution than the naive approach of applying a brutal force strategy and compare each query range with all the others and check if, according to the values of the relative bounds, there is an overlap (total or partial) between them.
In making the search for nodes within the Augmented Interval Tree we will use the information we have added, relative to the maximum value of the upper bound found in the subtree of each node, to maximize the search performance and exclude unnecessary comparisons. The way we use it is the following: if the maximum value of the subtree of the left child of a node is lower than the starting point of the query range, then we can exclude from the comparison all the nodes in the entire subtree and go directly to the right subtree of the node.
class Interval implements Comparable<Interval> { private long start; private long end; private long max; private Interval left; private Interval right; public int compareTo(Interval i) { if (this.start < i.start) { return -1; } else if (this.start == i.start) { return this.end <= i.end ? -1 : 1; } else { return 1; } } }
public class AugmentedIntervalTree { private Interval root; public static Interval insertNode(Interval tmp, Interval newNode) { if (tmp == null) { tmp = newNode; return tmp; } // Update of the maximum extreme of the subtree // during insertion if (newNode.getEnd() > tmp.getMax()) { tmp.setMax(newNode.getEnd()); } if (tmp.compareTo(newNode) <= 0) { if (tmp.getRight() == null) { tmp.setRight(newNode); } else { insertNode(tmp.getRight(), newNode); } } else { if (tmp.getLeft() == null) { tmp.setLeft(newNode); } else { insertNode(tmp.getLeft(), newNode); } } return tmp; } }
public void intersectInterval(Interval tmp, Interval i, List<Interval> res) { if (tmp == null) { return; } if (!((tmp.getStart() > i.getEnd()) || (tmp.getEnd() < i.getStart()))) { if (res == null) { res = new ArrayList<Interval>(); } res.add(tmp); } if ((tmp.getLeft() != null) && (tmp.getLeft().getMax() >= i.getStart())) { this.intersectInterval(tmp.getLeft(), i, res); } this.intersectInterval(tmp.getRight(), i, res); }http://algs4.cs.princeton.edu/93intersection/IntervalST.java.html
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 }
// return an interval in data structure that intersects the given inteval;
public Interval1D search(Node x, Interval1D interval) { while (x != null) { if (interval.intersects(x.interval)) return x.interval; else if (x.left == null) x = x.right; else if (x.left.max < interval.min) x = x.right; else x = x.left; } return null; }
public boolean searchAll(Node x, Interval1D interval, LinkedList<Interval1D> list) { boolean found1 = false; boolean found2 = false; boolean found3 = false; if (x == null) return false; if (interval.intersects(x.interval)) { list.add(x.interval); found1 = true; } if (x.left != null && x.left.max >= interval.min) found2 = searchAll(x.left, interval, list); if (found2 || x.left == null || x.left.max < interval.min) found3 = searchAll(x.right, interval, list); return found1 || found2 || found3; }http://www.sanfoundry.com/java-program-implement-interval-tree/
http://turing.plymouth.edu/~zshen/Webfiles/notes/CS322/CodeSample/com/mhhe/clrs2e/IntervalTree.java
Interval Tree - GeeksforGeeks
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.
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 is sorted by left point.
If search goest to right, then there is no intersection in left.
Because in this case, either left tree is empty or max of left tree is lesser than(<) low, so no intersect in left tree.
If search goes to left, then there is either an intersection in left, or no intersection in either.
In latter case, because there is no intersection in left,
and say the interval with max value is [c-max],
then x.high must be lesser than c, otherwise x would be intersected with [c-max].
So x.high must be lesser than all left values in right trees, so no intersection with right tree.
Interval Tree: 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.
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.
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.
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.
How does the above algorithm work?
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.
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.
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.
// A utility function to insert a new Interval Search Tree Node// This is similar to BST Insert. Here the low value of interval// is used tomaintain BST propertyITNode *insert(ITNode *root, Interval i){ // Base case: Tree is empty, new node becomes root if (root == NULL) return newNode(i); // Get low value of interval at root int l = root->i->low; // If root's low value is smaller, then new interval goes to // left subtree if (i.low < l) root->left = insert(root->left, i); // Else, new node goes to right subtree. else root->right = insert(root->right, i); // Update the max value of this ancestor if needed if (root->max < i.high) root->max = i.high; return root;}// A utility function to check if given two intervals overlapbool doOVerlap(Interval i1, Interval i2){ if (i1.low <= i2.high && i2.low <= i1.high) return true; return false;}// The main function that searches a given interval i in a given// Interval Tree.Interval *intervalSearch(ITNode *root, Interval i){ // Base Case, tree is empty if (root == NULL) return NULL; // If given interval overlaps with root if (doOVerlap(*(root->i), i)) return root->i; // If left child of root is present and max of left child is // greater than or equal to given interval, then i may // overlap with an interval is left subtree if (root->left != NULL && root->left->max >= i.low) return intervalSearch(root->left, i); // Else interval can only overlap with right subtree return intervalSearch(root->right, i);}
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.
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.
Exercise:
1) Implement delete operation for interval tree.
2) Extend the intervalSearch() to print all overlapping intervals instead of just one.
1) Implement delete operation for interval tree.
2) Extend the intervalSearch() to print all overlapping intervals instead of just one.
Video: 11 4 Interval Search Trees 1347
http://tribble.googlecode.com/svn/trunk/src/org/broad/tribble/index/interval/IntervalTree.java
http://algs4.cs.princeton.edu/93intersection/IntervalST.java.htmlhttp://tribble.googlecode.com/svn/trunk/src/org/broad/tribble/index/interval/IntervalTree.java
http://www.dgp.toronto.edu/people/JamesStewart/378notes/22intervals/
Read full article from Interval Tree - GeeksforGeeks
