range tree

Uses your system voice; voice and rate in settings.

Q818944Snapshot

≈ 5 min read

Names in other languages

  • Françaisarbre de portée
  • DeutschBereichsbaum
  • فارسیدرخت محدوده
  • Englishrange tree

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

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. Similar data structures were discovered independently by Lueker, Lee and Wong, and Willard. 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) O(\log^dn+k) but worse storage of O(n\log^{d-1} n) , 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 O(\log^{d-1} n + k) and space complexity O\left(n\left(\frac{\log n}{\log\log n}\right)^{d-1}\right) .

Evidence and sources

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. Similar data structures were discovered independently by Lueker, Lee and Wong, and Willard. 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) O(\log^dn+k) but worse storage of O(n\log^{d-1} n) , 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 O(\log^{d-1} n + k) and space complexity O\left(n\left(\frac{\log n}{\log\log n}\right)^{d-1}\right) .

[[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 O(\log n) . 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 O(\log n + k) , 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 O(\log n) (d−1)-dimensional range queries, it follows that the time required to perform a d-dimensional range query is O(\log^{d} n + k) , where k is the number of points in the query interval.

This can be reduced to O(\log^{d - 1} n + k) using a variant of fractional cascading.

Text derived from https://en.wikipedia.org/w/index.php?oldid=1372523078 under CC BY-SA 4.0; modifications have been made.

Provenance

snapshot range-tree-094019-fbaa8f4fd18414dc · hash fbaa8f4fd18414dc129bfd4286271d98bdf082c6f0a223f89613bc320677465b · captured 1788223625.0 · version history

Cite this page as: encyclopegia.org, “range tree”, snapshot range-tree-094019-fbaa8f4fd18414dc. https://encyclopegia.org/a/range-tree

Sources cited in this revision

No external citation was extracted for this revision. That is a statement about the source, not a claim that none exists.