Interval tree

In computer science, an interval tree is a tree data structure to hold intervals. Specifically, it allows one to efficiently find all intervals that overlap with any given interval or point. It is 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. A similar data structure is the segment tree. The trivial solution to finding all overlapping intervals is to visit each interval and test whether it intersects the given point or interval, which requires O(n) time, where n is the number of intervals in the collection. Since a query may return all intervals, for example if the query is a large interval intersecting all intervals in the collection, this is asymptotically optimal; however, output-sensitive algorithms, where the runtime is expressed in terms of m (the number of intervals produced by the query) may also be considered. Interval trees have a query time of O(\log n + m) and an initial creation time of O(n \log n) , while limiting memory consumption to O(n) . After creation, interval trees may be dynamic, allowing efficient insertion and deletion of an interval in O(\log n) time.…

In computer science, an interval tree is a tree data structure to hold intervals. Specifically, it allows one to efficiently find all intervals that overlap with any given interval or point. It is 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. A similar data structure is the segment tree. The trivial solution to finding all overlapping intervals is to visit each interval and test whether it intersects the given point or interval, which requires O(n) time, where n is the number of intervals in the collection. Since a query may return all intervals, for example if the query is a large interval intersecting all intervals in the collection, this is asymptotically optimal; however, output-sensitive algorithms, where the runtime is expressed in terms of m (the number of intervals produced by the query) may also be considered. Interval trees have a query time of O(\log n + m) and an initial creation time of O(n \log n) , while limiting memory consumption to O(n) . After creation, interval trees may be dynamic, allowing efficient insertion and deletion of an interval in O(\log n) time. If the endpoints of intervals are within a small integer range (e.g., in the range [1, \ldots, O(n)] ), faster and in fact optimal data structures exist with preprocessing time O(n) and query time O(1+ m) for reporting m intervals containing a given query point (see for a very simple one). ==Naïve approach== In a simple case, the intervals do not overlap and they can be inserted into a simple binary search tree and queried in O(\log n) time. However, with arbitrarily overlapping intervals, there is no way to compare two intervals for insertion into the tree since orderings sorted by the beginning points or the ending points may be different. A naïve approach might be to build two parallel trees, one ordered by the beginning point, and one ordered by the ending point of each interval. This allows discarding half of each tree in O(\log n) time, but the results must be merged, requiring O(n) time. This returns queries in O( n + \log n) = O( n) , which is no better than brute-force. Interval trees solve this problem. This article describes two alternative designs for an interval tree, dubbed the centered interval tree and the augmented tree. ===Java example: Adding a new interval to the tree=== The key of each node is the interval itself, hence nodes are ordered first by low value and finally by high value, and the value of each node is the end point of the interval: public void add(Interval i) { put(i, i.getEnd()); } ===Java example: Searching a point or an interval in the tree=== To search for an interval, one walks the tree, using the key ( n.getKey() ) and high value ( n.getValue() ) to omit any branches that cannot overlap the query. The simplest case is a point query: // Search for all intervals containing "p", starting with the // node "n" and adding matching intervals to the list "result" public void search(IntervalNode n, Point p, List result) { // Don't search nodes that don't exist if (n == null) return; // If p is to the right of the rightmost point of any interval // in this node and all children, there won't be any matches. if (p.compareTo(n.getValue()) > 0) return; // Search left children search(n.getLeft(), p, result); // Check this node if (n.getKey().contains(p)) result.add(n.getKey()); // If p is to the left of the start of this interval, // then it can't be in any child to the right. if (p.compareTo(n.getKey().getStart()) where a.compareTo(b) returns a negative value if a a.compareTo(b) returns zero if a = b a.compareTo(b) returns a positive value if a > b The code to search for an interval is similar, except for the check in the middle: // Check this node if (n.getKey().overlapsWith(i)) result.add (n.getKey()); overlapsWith() is defined as: public boolean overlapsWith(Interval other) { return start.compareTo(other.getEnd()) = 0; } ===Higher dimensions=== Augmented trees can be extended to higher dimensions by cycling through the dimensions at each level of the tree. For example, for two dimensions, the odd levels of the tree might contain ranges for the x-coordinate, while the even levels contain ranges for the y-coordinate. This approach effectively converts the data structure from an augmented binary tree to an augmented kd-tree, thus significantly complicating the balancing algorithms for insertions and deletions. A simpler solution is to use nested interval trees. First, create a tree using the ranges for the y-coordinate. Now, for each node in the tree, add another interval tree on the x-ranges, for all elements whose y-range is the same as that node's y-range. The advantage of this solution is that it can be extended to an arbitrary number of dimensions using the same code base. At first, the additional cost of the nested trees might seem prohibitive, but this is usually not so. As with the non-nested solution earlier, one node is needed per x-coordinate, yielding the same number of nodes for both solutions. The only additional overhead is that of the nested tree structures, one per vertical interval. This structure is usually of negligible size, consisting only of a pointer to the root node, and possibly the number of nodes and the depth of the tree. ==Medial- or length-oriented tree== A medial- or length-oriented tree is similar to an augmented tree, but symmetrical, with the binary search tree ordered by the medial points of the intervals. There is a maximum-oriented binary heap in every node, ordered by the length of the interval (or half of the length). Also we store the minimum and maximum possible value of the subtree in each node (thus the symmetry). ===Overlap test=== Using only start and end values of two intervals \left( a_{i}, b_i \right) , for i=0,1 , the overlap test can be performed as follows: a_0 and a_1 This can be simplified using the sum and difference: s_i = a_i + b_i d_i = b_i - a_i Which reduces the overlap test to: \left| s_1 - s_0 \right| ===Adding interval=== Adding new intervals to the tree is the same as for a binary search tree using the medial value as the key. We push d_i onto the binary heap associated with the node, and update the minimum and maximum possible values associated with all higher nodes. ===Searching for all overlapping intervals=== Let's use a_q, b_q, m_q, d_q for the query interval, and M_n for the key of a node (compared to m_i of intervals) Starting with root node, in each node, first we check if it is possible that our query interval overlaps with the node subtree using minimum and maximum values of node (if it is not, we don't continue for this node). Then we calculate \min \left\{ d_i \right\} for intervals inside this node (not its children) to overlap with query interval (knowing m_i = M_n ): \min \left\{ d_i \right\} = \left| m_q - M_n \right| - d_q and perform a query on its binary heap for the d_i 's bigger than \min \left\{ d_i \right\} Then we pass through both left and right children of the node, doing the same thing. In the worst-case, we have to scan all nodes of the binary search tree, but since binary heap query is optimum, this is acceptable (a 2- dimensional problem can not be optimum in both dimensions) This algorithm is expected to be faster than a traditional interval tree (augmented tree) for search operations. Adding elements is a little slower in practice, though the order of growth is the same.

Text derived from https://en.wikipedia.org/w/index.php?oldid=1378431441 under CC BY-SA 4.0; modifications have been made.