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.

Compared to k-d trees, range trees offer faster query times of (in Big O notation)

In 1990, Bernard Chazelle improved this to query time

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.

This construction time can be improved for 2-dimensional range trees to

Let SL be the set of points with x-coordinate less than or equal to xm and let SR be the set of points with x-coordinate greater than xm.

Create a vertex v with left-child vL and right-child vR.

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

To report the points that lie in the interval [x1, x2], we start by searching for x1 and x2.

At some vertex in the tree, the search paths to x1 and x2 will diverge.

Let vsplit be the last vertex that these two search paths have in common.

For every vertex v in the search path from vsplit to x1, if the value stored at v is greater than x1, 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 x2 along the search path from vsplit to x2, and report the leaf of this path if it lies within the query interval.

Reporting all of the points stored in the subtree of a vertex can be done in linear time using any tree traversal algorithm.

Eventually, a 1-dimensional range query will be performed and the correct points will be reported.

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