“Range tree”的意思、由来-开放百科全书

In computer science, a range tree is an ordered tree data structure to hold a list of points. It allows all points within a given range to be reported efficiently, and is typically used in two or higher dimensions. Range trees were introduced by Jon Louis Bentley in 1979.^[1] Similar data structures were discovered independently by Lueker,^[2] Lee and Wong,^[3] and Willard.^[4]

The range tree is an alternative to the k-d tree. Compared to k-d trees, range trees offer faster query times of (in Big O notation)

but worse storage of

, where n is the number of points stored in the tree, d is the dimension of each point and k is the number of points reported by a given query.

Data structure

A range tree on a set of 1-dimensional points is a balanced binary search tree on those points. The points stored in the tree are stored in the leaves of the tree; each internal node stores the largest value contained in its left subtree.

A range tree on a set of points in d-dimensions is a recursively defined multi-level binary search tree. Each level of the data structure is a binary search tree on one of the d-dimensions.

The first level is a binary search tree on the first of the d-coordinates. Each vertex v of this tree contains an associated structure that is a (d−1)-dimensional range tree on the last (d−1)-coordinates of the points stored in the subtree of v.

Operations

Construction

A 1-dimensional range tree on a set of n points is a binary search tree, which can be constructed in

time. Range trees in higher dimensions are constructed recursively by constructing a balanced binary search tree on the first coordinate of the points, and then, for each vertex v in this tree, constructing a (d−1)-dimensional range tree on the points contained in the subtree of v. Constructing a range tree this way would require

time.

Let S be a set of n 2-dimensional points. If S contains only one point, return a leaf containing that point. Otherwise, construct the associated structure of S, a 1-dimensional range tree on the y-coordinates of the points in S. Let x_m be the median x-coordinate of the points. Let S_L be the set of points with x-coordinate less than or equal to x_m and let S_R be the set of points with x-coordinate greater than x_m. Recursively construct v_L, a 2-dimensional range tree on S_L, and v_R, a 2-dimensional range tree on S_R. Create a vertex v with left-child v_L and right-child v_R.

If we sort the points by their y-coordinates at the start of the algorithm, and maintain this ordering when splitting the points by their x-coordinate, we can construct the associated structures of each subtree in linear time.

This reduces the time to construct a 2-dimensional range tree to

, and also reduces the time to construct a d-dimensional range tree to

Range queries

A range query on a range tree reports the set of points that lie inside a given interval. To report the points that lie in the interval [x₁, x₂], we start by searching for x₁ and x₂. At some vertex in the tree, the search paths to x₁ and x₂ will diverge. Let v_split be the last vertex that these two search paths have in common. For every vertex v in the search path from v_split to x₁, if the value stored at v is greater than x₁, report every point in the right-subtree of v. If v is a leaf, report the value stored at v if it is inside the query interval. Similarly, reporting all of the points stored in the left-subtrees of the vertices with values less than x₂ along the search path from v_split to x₂, and report the leaf of this path if it lies within the query interval.

Since the range tree is a balanced binary tree, the search paths to x₁ and x₂ have length

. Reporting all of the points stored in the subtree of a vertex can be done in linear time using any tree traversal algorithm. It follows that the time to perform a range query is

, where k is the number of points in the query interval.

Range queries in d-dimensions are similar. Instead of reporting all of the points stored in the subtrees of the search paths, perform a (d−1)-dimensional range query on the associated structure of each subtree. Eventually, a 1-dimensional range query will be performed and the correct points will be reported. Since a d-dimensional query consists of

(d−1)-dimensional range queries, it follows that the time required to perform a d-dimensional range query is

, where k is the number of points in the query interval. This can be reduced to

using a variant of fractional cascading.^[2]^[4]^[7]

See also

References

1. ^{{Cite journal | last1 = Bentley | first1 = J. L. | title = Decomposable searching problems | doi = 10.1016/0020-0190(79)90117-0 | journal = Information Processing Letters | volume = 8 | issue = 5 | pages = 244–251 | year = 1979 | pmid = | pmc = | url = http://www.dtic.mil/get-tr-doc/pdf?AD=ADA061627 }}
2. ^¹{{Cite book | last1 = Lueker | first1 = G. S. | chapter = A data structure for orthogonal range queries | doi = 10.1109/SFCS.1978.1 | title = 19th Annual Symposium on Foundations of Computer Science (sfcs 1978) | pages = 28–21 | year = 1978 | pmid = | pmc = }}
3. ^{{Cite journal | last1 = Lee | first1 = D. T. | last2 = Wong | first2 = C. K. | doi = 10.1145/320613.320618 | title = Quintary trees: A file structure for multidimensional database systems | journal = ACM Transactions on Database Systems | volume = 5 | issue = 3 | pages = 339 | year = 1980 | pmid = | pmc = }}
4. ^¹{{cite techreport | first = Dan E. | last = Willard | title = The super-b-tree algorithm | number = TR-03-79 | publisher = Aiken Computer Lab, Harvard University | location = Cambridge, MA}}
5. ^{{cite journal|last1=Chazelle|first1=Bernard|title=Lower Bounds for Orthogonal Range Searching: I. The Reporting Case|journal=ACM|date=1990|volume=37|pages=200-212|url=http://www.cs.princeton.edu/~chazelle/pubs/LBOrthoRangeSearchReporting.pdf}}
6. ^{{cite journal|last1=Chazelle|first1=Bernard|title=Lower Bounds for Orthogonal Range Searching: II. The Arithmetic Model|journal=ACM|date=1990|volume=37|pages=439-463|url=http://www.cs.princeton.edu/~chazelle/pubs/LBOrthoRangeSearchArithmetic.pdf}}
7. ^¹{{Cite book | title = Computational Geometry | first1 = Mark| last1 = de Berg| first2 = Otfried| last2 = Cheong| first3 = Marc| last3 = van Kreveld| first4 = Mark| last4 = Overmars| doi = 10.1007/978-3-540-77974-2 | year = 2008 | isbn = 978-3-540-77973-5 | pmid = | pmc = }}

Data structure

Operations

Construction

Range queries

See also

References

External links