Range tree

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(log² 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.

References

• Mark de Berg, Marc van Krevald, Mark Overmars, and Otfried Schwarzkopf. Computational Geometry, Second Revised Edition. Springer-Verlag 2000. Section 5.3: Range Trees, pp.105-110.