Range tree

A range tree (English range tree ) is a data structure for storing a set of points in k- dimensional real space. It is used in computer science in the field of computational geometry and efficiently supports orthogonal range queries.

Field of application

Application find such data structures in geographic information systems. Here they are used to locate geographic objects. Manage geographic information systems, the spatial coordinates of these objects. The range tree is divided ( partitioned ) is now the objects depending on their coordinates into subsets. This can later be limited to a small area and thus greatly accelerate the search for a specified object. Such data structures are referred to as an index structure.

Mathematical Description

In the simplest case, ie the one-dimensional range tree is an ordinary binary search tree. In general, the k-dimensional range tree is defined recursively:

{} Are the coordinate axes of the

• First, construct a 1-dimensional range tree for the coordinate axis, ie for 1-dimensional points that arise by cutting the rear k-1 coordinates. Each node being associated with an interval which extends from the smallest to the largest number that is stored in the subtree of the node.
• Construct recursively for each internal node of each a (k -1 )-dimensional range tree from the ( k-1 )-dimensional points that are contained in the subtree with root and as a result by cutting off the first coordinate.
• Connect the nodes with the help of a pointer to the associated

The area tree thus constructed supports orthogonal range queries in