R-tree

(data structure)

Definition: (1) A spatial access method that splits space with hierarchically nested, and possibly overlapping, boxes. The tree is height-balanced. (2) A recursion tree.

See also B-tree, P-tree (2), P-tree (3), R⁺-tree, R^*-tree.

Author: PEB

Implementation

(1) Ondřej Pavlata's Mg R-tree library(C++).

More information

(1) A. Guttman, R-trees: A Dynamic Index Structure for Spatial Searching, Proc ACM SIGMOD International Conference on Management of Data, 47-57, June 1984.
(2) Used in [GCG92]. Suggested by Rama Maiti, 19 August 2001.

Go to the Dictionary of Algorithms and Data Structures home page.

If you have suggestions, corrections, or comments, please get in touch with Paul E. Black.

Entry modified 26 May 2011.
HTML page formatted Tue Dec 6 16:16:32 2011.

Cite this as:
Paul E. Black, "R-tree", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed., U.S. National Institute of Standards and Technology. 26 May 2011. (accessed TODAY) Available from: http://www.nist.gov/dads/HTML/rtree.html