Range tree
Encyclopedia
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 efficiently retrieved, and is typically used in two or higher dimensions.
It is similar to a kd-tree
except with faster query times of O
(logd n + k) but worse storage of O(n log(d-1) n), with d being the dimension of the space, n being the number of points in the tree, and k being the number of points retrieved for a given query.
Range trees may be contrasted with interval tree
s: instead of storing points and allowing points in a given range to be retrieved efficiently, an interval tree stores intervals and allows the intervals containing a given point to be retrieved efficiently.
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
, a range tree is an ordered tree data structure
Data structure
In computer science, a data structure is a particular way of storing and organizing data in a computer so that it can be used efficiently.Different kinds of data structures are suited to different kinds of applications, and some are highly specialized to specific tasks...
to hold a list of points. It allows all points within a given range to be efficiently retrieved, and is typically used in two or higher dimensions.
It is similar to a kd-tree
Kd-tree
In computer science, a k-d tree is a space-partitioning data structure for organizing points in a k-dimensional space. k-d trees are a useful data structure for several applications, such as searches involving a multidimensional search key...
except with faster query times of O
Big O notation
In mathematics, big O notation is used to describe the limiting behavior of a function when the argument tends towards a particular value or infinity, usually in terms of simpler functions. It is a member of a larger family of notations that is called Landau notation, Bachmann-Landau notation, or...
(logd n + k) but worse storage of O(n log(d-1) n), with d being the dimension of the space, n being the number of points in the tree, and k being the number of points retrieved for a given query.
Range trees may be contrasted with interval tree
Interval tree
In computer science, an interval tree is an ordered tree data structure to hold intervals. Specifically, it allows one to efficiently find all intervals that overlap with any given interval or point. It is often used for windowing queries, for example, to find all roads on a computerized map inside...
s: instead of storing points and allowing points in a given range to be retrieved efficiently, an interval tree stores intervals and allows the intervals containing a given point to be retrieved efficiently.
External links
- Range and Segment Trees in CGALCGALThe Computational Geometry Algorithms Library is a software library that aims to provide easy access to efficient and reliable algorithms in computational geometry. While primarily written in C++, Python and Scilab bindings are also available....
, the Computational Geometry Algorithms Library.