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.
(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.
If you have suggestions, corrections, or comments, please get in touch with Paul Black.
Entry modified 26 May 2011.
HTML page formatted Fri Feb 23 10:06:08 2018.
Cite this as:
Paul E. Black, "R-tree", in Dictionary of Algorithms and Data Structures [online], Vreda Pieterse and Paul E. Black, eds. 26 May 2011. (accessed TODAY) Available from: https://www.nist.gov/dads/HTML/rtree.html