# Range tree

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Range_tree
> Markdown URL: https://mediated.wiki/source/Range_tree.md
> Source: https://en.wikipedia.org/wiki/Range_tree
> Source revision: 1318224186
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

{{Short description|Ordered tree data structure}}
{{Infobox data structure
|name=Range tree
|type=tree
|invented_by= [Jon Louis Bentley](/source/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](/source/computer_science), a '''range tree''' is an [ordered tree](/source/ordered_tree_data_structure) [data structure](/source/data_structure) to hold a list of points. It allows all points within a given range to be [reported](/source/Range_query_(computer_science)) efficiently, and is typically used in two or higher dimensions. Range trees were introduced by [Jon Louis Bentley](/source/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](/source/k-d_tree). Compared to ''k''-d trees, range trees offer faster query times of (in [Big O notation](/source/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](/source/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](/source/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](/source/recursive_data_type) multi-level [binary search tree](/source/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''<sub>m</sub> be the median ''x''-coordinate of the points. Let ''S''<sub>L</sub> be the set of points with ''x''-coordinate less than or equal to ''x''<sub>m</sub> and let ''S''<sub>R</sub> be the set of points with ''x''-coordinate greater than ''x''<sub>m</sub>. Recursively construct ''v''<sub>L</sub>, a 2-dimensional range tree on ''S''<sub>L</sub>, and ''v''<sub>R</sub>, a 2-dimensional range tree on ''S''<sub>R</sub>. Create a vertex ''v'' with left-child ''v''<sub>L</sub> and right-child ''v''<sub>R</sub>.
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''<sub>1</sub>, ''x''<sub>2</sub>]. Points stored in the subtrees shaded in gray will be reported. find(''x''<sub>1</sub>) and find(''x''<sub>2</sub>) will be reported if they are inside the query interval.]]

A [range query](/source/range_query_(data_structures)) 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''<sub>1</sub>, ''x''<sub>2</sub>], we start by searching for ''x''<sub>1</sub> and ''x''<sub>2</sub>. At some vertex in the tree, the search paths to ''x''<sub>1</sub> and ''x''<sub>2</sub> will diverge. Let ''v''<sub>split</sub> be the last vertex that these two search paths have in common. For every vertex ''v'' in the search path from ''v''<sub>split</sub> to ''x''<sub>1</sub>, if the value stored at ''v'' is greater than ''x''<sub>1</sub>, 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''<sub>2</sub> along the search path from ''v''<sub>split</sub> to ''x''<sub>2</sub>, 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''<sub>1</sub> and ''x''<sub>2</sub> 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](/source/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](/source/fractional_cascading).<ref name=Lueker78 /><ref name=Willard79 /><ref name=DutchBook3E />

== See also ==

* [''k''-d tree](/source/k-d_tree)
* [Segment tree](/source/Segment_tree)
* [Range searching](/source/Range_searching)

== References ==
{{Reflist}}

== External links ==
* [http://www.cgal.org/Manual/latest/doc_html/cgal_manual/SearchStructures/Chapter_main.html Range and Segment Trees] in [CGAL](/source/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](/source/PAM_library), the parallel augmented map library.
* [https://zhoujoseph.github.io/Orthogonal-range-tree-visualization/ 2D Range Tree Visualization],  Zhou Kaixuan.

{{CS-Trees}}

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

---
Adapted from the Wikipedia article [Range tree](https://en.wikipedia.org/wiki/Range_tree) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Range_tree?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.