Range tree
Type	tree
Invented	1979
Invented by	Jon Louis Bentley
Time complexity inbig O notation Operation Average Worst case Search ${\displaystyle O({\log }^{d}n+k)}$ ${\displaystyle O({\log }^{d}n+k)}$ Space complexity Space ${\displaystyle O(n{\log }^{d-1}n)}$ ${\displaystyle O(n{\log }^{d-1}n)}$

Incomputer science, arange tree is anordered treedata structure to hold a list of points. It allows all points within a given range to bereported efficiently, and is typically used in two or higher dimensions. Range trees were introduced byJon 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 thek-d tree. Compared tok-d trees, range trees offer faster query times of (inBig O notation)${\displaystyle O({\log }^{d}n+k)}$ but worse storage of${\displaystyle O(n{\log }^{d-1}n)}$, wheren is the number of points stored in the tree,d is the dimension of each point andk is the number of points reported by a given query.

In 1990,Bernard Chazelle improved this to query time${\displaystyle O({\log }^{d-1}n+k)}$ and space complexity${\displaystyle O\left(n{\left(\frac{\log n}{\log \log n}\right)}^{d-1}\right)}$.^[5][6]

A range tree on a set of 1-dimensional points is a balancedbinary 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 ind-dimensions is arecursively defined multi-levelbinary search tree. Each level of the data structure is a binary search tree on one of thed-dimensions.The first level is a binary search tree on the first of thed-coordinates. Each vertexv 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 ofv.

A 1-dimensional range tree on a set ofn points is a binary search tree, which can be constructed in${\displaystyle O(n\log n)}$ 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 vertexv in this tree, constructing a (d−1)-dimensional range tree on the points contained in the subtree ofv. Constructing a range tree this way would require${\displaystyle O(n{\log }^{d}n)}$ time.

This construction time can be improved for 2-dimensional range trees to${\displaystyle O(n\log n)}$.^[7]LetS be a set ofn 2-dimensional points. IfS contains only one point, return a leaf containing that point. Otherwise, construct the associated structure ofS, a 1-dimensional range tree on they-coordinates of the points inS. Letx_m be the medianx-coordinate of the points. LetS_L be the set of points withx-coordinate less than or equal tox_m and letS_R be the set of points withx-coordinate greater thanx_m. Recursively constructv_L, a 2-dimensional range tree onS_L, andv_R, a 2-dimensional range tree onS_R. Create a vertexv with left-childv_L and right-childv_R.If we sort the points by theiry-coordinates at the start of the algorithm, and maintain this ordering when splitting the points by theirx-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${\displaystyle O(n\log n)}$, and also reduces the time to construct ad-dimensional range tree to${\displaystyle O(n{\log }^{d-1}n)}$.

Arange 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 forx₁ andx₂. At some vertex in the tree, the search paths tox₁ andx₂ will diverge. Letv_split be the last vertex that these two search paths have in common. For every vertexv in the search path fromv_split tox₁, if the value stored atv is greater thanx₁, report every point in the right-subtree ofv. Ifv is a leaf, report the value stored atv if it is inside the query interval. Similarly, reporting all of the points stored in the left-subtrees of the vertices with values less thanx₂ along the search path fromv_split tox₂, 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 tox₁ andx₂ have length${\displaystyle O(\log n)}$. Reporting all of the points stored in the subtree of a vertex can be done in linear time using anytree traversal algorithm. It follows that the time to perform a range query is${\displaystyle O(\log n+k)}$, wherek is the number of points in the query interval.

Range queries ind-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 ad-dimensional query consists of${\displaystyle O(\log n)}$ (d−1)-dimensional range queries, it follows that the time required to perform ad-dimensional range query is${\displaystyle O({\log }^{d}n+k)}$, wherek is the number of points in the query interval. This can be reduced to${\displaystyle O({\log }^{d-1}n+k)}$ using a variant offractional cascading.^[2][4][7]

• k-d tree
• Segment tree
• Range searching

• Range and Segment Trees inCGAL, the Computational Geometry Algorithms Library.
• Lecture 8: Range Trees, Marc van Kreveld. Archivedhere.
• Range Trees usingPAM, the parallel augmented map library.
• 2D Range Tree Visualization, Zhou Kaixuan.

• Trees (data structures)
• Geometric data structures