Range tree

{{Short description|Ordered tree data structure}} {{Infobox data structure |name=Range tree |type=tree |invented_by= Jon Louis Bentley |invented_year=1979 |space_avg=<math>O(n \log^{d - 1} n)</math> |space_worst=<math>O(n \log^{d - 1} n)</math> |search_avg=<math>O(\log^d n + k)</math> |search_worst=<math>O(\log^d n + k)</math> }}

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.<ref name=Bentley79>{{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 | url = https://apps.dtic.mil/sti/pdfs/ADA061627.pdf | archive-url = https://web.archive.org/web/20170924023643/http://www.dtic.mil/get-tr-doc/pdf?AD=ADA061627 | url-status = live | archive-date = September 24, 2017 }}</ref> Similar data structures were discovered independently by Lueker,<ref name=Lueker78>{{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 | s2cid = 14970942 }}</ref> Lee and Wong,<ref name=LeeWong80>{{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 | s2cid = 2547376 }}</ref> and Willard.<ref name=Willard79>{{cite tech report | first = Dan E. | last = Willard | title = The super-''b''-tree algorithm | number = TR-03-79 | publisher = Aiken Computer Lab, Harvard University | location = Cambridge, MA}}</ref> 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) <math>O(\log^dn+k)</math> but worse storage of <math>O(n\log^{d-1} n)</math>, 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.

In 1990, Bernard Chazelle improved this to query time <math>O(\log^{d-1} n + k)</math> and space complexity <math>O\left(n\left(\frac{\log n}{\log\log n}\right)^{d-1}\right)</math>.<ref name=Chazelle90_1>{{cite journal|last1=Chazelle|first1=Bernard|title=Lower Bounds for Orthogonal Range Searching: I. The Reporting Case|journal=Journal of the ACM|date=1990|volume=37|issue=2 |pages=200–212|url=https://www.cs.princeton.edu/~chazelle/pubs/LBOrthoRangeSearchReporting.pdf|doi=10.1145/77600.77614|s2cid=8895683 }}</ref><ref name=Chazelle90_2>{{cite journal|last1=Chazelle|first1=Bernard|title=Lower Bounds for Orthogonal Range Searching: II. The Arithmetic Model|journal=Journal of the ACM|date=1990|volume=37|pages=439–463|url=https://www.cs.princeton.edu/~chazelle/pubs/LBOrthoRangeSearchArithmetic.pdf|doi=10.1145/79147.79149|s2cid=15935619 }}</ref>

== Data structure ==

thumb|upright=2.0|alt=An example of a 1-dimensional range tree.|An example of a 1-dimensional range tree. Each node which is not a leaf stores the largest value of its left subtree.

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 of 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 <math>O(n \log n)</math> 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 <math>O(n \log ^d n)</math> time.

This construction time can be improved for 2-dimensional range trees to <math>O(n \log n)</math>.<ref name="DutchBook3E">{{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 }}</ref> 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 <math>O(n \log n)</math>, and also reduces the time to construct a ''d''-dimensional range tree to <math>O(n \log^{d - 1} n)</math>.

=== Range queries ===

[[File:1-dimensional-range-query.svg|thumb|upright=1.0|alt=A 1-dimensional range query.|A 1-dimensional range query [''x''1, ''x''2]. Points stored in the subtrees shaded in gray will be reported. find(''x''1) and find(''x''2) will be reported if they are inside the query interval.]]

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''1, ''x''2], we start by searching for ''x''1 and ''x''2. At some vertex in the tree, the search paths to ''x''1 and ''x''2 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''1, if the value stored at ''v'' is greater than ''x''1, 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''2 along the search path from ''v''split to ''x''2, 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''1 and ''x''2 have length <math>O(\log n)</math>. 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 <math>O(\log n + k)</math>, 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 <math>O(\log n)</math> (''d''−1)-dimensional range queries, it follows that the time required to perform a ''d''-dimensional range query is <math>O(\log^{d} n + k)</math>, where ''k'' is the number of points in the query interval. This can be reduced to <math>O(\log^{d - 1} n + k)</math> using a variant of fractional cascading.<ref name=Lueker78 /><ref name=Willard79 /><ref name=DutchBook3E />

== References == {{Reflist}}

== External links == * [http://www.cgal.org/Manual/latest/doc_html/cgal_manual/SearchStructures/Chapter_main.html Range and Segment Trees] in CGAL, the Computational Geometry Algorithms Library. * [http://www.cs.uu.nl/docs/vakken/ga/2021/slides/slides5b.pdf Lecture 8: Range Trees], Marc van Kreveld. Archived [https://archive.today/20230906153801/http://www.cs.uu.nl/docs/vakken/ga/2021/slides/slides5b.pdf here]. * [https://github.com/syhlalala/PAM/tree/master/range_query Range Trees] using PAM, the parallel augmented map library. * [https://zhoujoseph.github.io/Orthogonal-range-tree-visualization/ 2D Range Tree Visualization], Zhou Kaixuan.

Category:Trees (data structures) Category:Geometric data structures