Range tree
From Wikipedia, the free 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(log2 n + k) but worse storage of O(n log n), with n being the number of points in the tree, and k being the number of points retrieved for a given query.
[edit] References
- Mark de Berg, Marc van Kreveld, Mark Overmars, and Otfried Schwarzkopf. Computational Geometry, Second Revised Edition. Springer-Verlag 2000. Section 5.3: Range Trees, pp.105-110.
