Интервал ағашы: аралықтарды сақтау және іздеу құрылымы

Tree data structure to hold intervals
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 is to visit each interval and test whether it intersects the given point or interval, which requires time, where 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, we can do better by considering output sensitive algorithms, where the runtime is expressed in terms of , the number of intervals produced by the query. Interval trees have a query time of and an initial creation time of , while limiting memory consumption to After creation, interval trees may be dynamic, allowing efficient insertion and deletion of an interval in time. If the endpoints of intervals are within a small integer range (e. g., in the range ), faster and in fact optimal data structures exist with preprocessing time and query time for reporting intervals containing a given query point (see for a very simple one).

In a simple case, the intervals do not overlap and they can be inserted into a simple binary search tree and queried in 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 naive 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 time, but the results must be merged, requiring time. This gives us queries in , 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.

Queries require time, with being the total number of intervals and being the number of reported results. Construction requires time, and storage requires space.

Given the data structure constructed above, we receive queries consisting of ranges or points, and return all the ranges in the original set overlapping this input.

The task is to find all intervals in the tree that overlap a given point The tree is walked with a similar recursive algorithm as would be used to traverse a traditional binary tree, but with extra logic to support searching the intervals overlapping the "center" point at each node. For each tree node, is compared to , the midpoint used in node construction above. If is less than , the leftmost set of intervals, , is considered. If is greater than , the rightmost set of intervals, , is considered. As each node is processed as we traverse the tree from the root to a leaf, the ranges in its are processed. If is less than , we know that all intervals in end after , or they could not also overlap Therefore, we need only find those intervals in that begin before We can consult the lists of that have already been constructed. Since we only care about the interval beginnings in this scenario, we can consult the list sorted by beginnings. Suppose we find the closest number no greater than in this list. All ranges from the beginning of the list to that found point overlap because they begin before and end after (as we know because they overlap which is larger than ). Thus, we can simply start enumerating intervals in the list until the startpoint value exceeds
Likewise, if is greater than , we know that all intervals in must begin before , so we find those intervals that end after using the list sorted by interval endings. If exactly matches , all intervals in can be added to the results without further processing and tree traversal can be stopped.

The interval tree data structure can be generalized to a higher dimension with identical query and construction time and space. First, a range tree in dimensions is constructed that allows efficient retrieval of all intervals with beginning and end points inside the query region Once the corresponding ranges are found, the only thing that is left are those ranges that enclose the region in some dimension. To find these overlaps, interval trees are created, and one axis intersecting is queried for each. For example, in two dimensions, the bottom of the square (or any other horizontal line intersecting ) would be queried against the interval tree constructed for the horizontal axis. Likewise, the left (or any other vertical line intersecting ) would be queried against the interval tree constructed on the vertical axis. Each interval tree also needs an addition for higher dimensions. At each node we traverse in the tree, is compared with to find overlaps. Instead of two sorted lists of points as was used in the one dimensional case, a range tree is constructed. This allows efficient retrieval of all points in that overlap region .

If after deleting an interval from the tree, the node containing that interval contains no more intervals, that node may be deleted from the tree. This is more complex than a normal binary tree deletion operation. An interval may overlap the center point of several nodes in the tree. Since each node stores the intervals that overlap it, with all intervals completely to the left of its center point in the left subtree, similarly for the right subtree, it follows that each interval is stored in the node closest to the root from the set of nodes whose center point it overlaps. Normal deletion operations in a binary tree (for the case where the node being deleted has two children) involve promoting a node further from the leaf to the position of the node being deleted (usually the leftmost child of the right subtree, or the rightmost child of the left subtree). As a result of this promotion, some nodes that were above the promoted node will become its descendants; it is necessary to search these nodes for intervals that also overlap the promoted node, and move those intervals into the promoted node. As a consequence, this may result in new empty nodes, which must be deleted, following the same algorithm again.

The same issues that affect deletion also affect rotation operations; rotation must preserve the invariant that nodes are stored as close to the root as possible.

Another way to represent intervals is described in
Both insertion and deletion require time, with being the total number of intervals in the tree prior to the insertion or deletion operation. An augmented tree can be built from a simple ordered tree, for example a binary search tree or self balancing binary search tree, ordered by the 'low' values of the intervals. An extra annotation is then added to every node, recording the maximum upper value among all the intervals from this node down. Maintaining this attribute involves updating all ancestors of the node from the bottom up whenever a node is added or deleted. This takes only O(h) steps per node addition or removal, where h is the height of the node added or removed in the tree. If there are any tree rotations during insertion and deletion, the affected nodes may need updating as well. Now, it is known that two intervals and overlap only when both and When searching the trees for nodes overlapping with a given interval, you can immediately skip:
all nodes to the right of nodes whose low value is past the end of the given interval. all nodes that have their maximum high value below the start of the given interval.

Some performance may be gained if the tree avoids unnecessary traversals. These can occur when adding intervals that already exist or removing intervals that don't exist. A total order can be defined on the intervals by ordering them first by their lower bounds and then by their upper bounds. Then, a membership check can be performed in time, versus the time required to find duplicates if intervals overlap the interval to be inserted or removed. This solution has the advantage of not requiring any additional structures. The change is strictly algorithmic. The disadvantage is that membership queries take time. Alternately, at the rate of memory, membership queries in expected constant time can be implemented with a hash table, updated in lockstep with the interval tree. This may not necessarily double the total memory requirement, if the intervals are stored by reference rather than by value.

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.

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).

Adding new intervals to the tree is the same as for a binary search tree using the medial value as the key. We push onto the binary heap associated with the node, and update the minimum and maximum possible values associated with all higher nodes.