R-tree

(data structure)

Definition: (1) A spatial access method which 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

(Java).

More information

(1) After [GG98]. Also found in Algorithms and Theory of Computation Handbook, page 18-24. (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 17 December 2007.
HTML page formatted Mon Dec 17 12:47:01 2007.

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. 17 December 2007. (accessed TODAY) Available from: http://www.nist.gov/dads/HTML/rtree.html