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 reported efficiently, and is typically used in two or higher dimensions. Range trees were introduced by Jon Louis Bentley in 1979. Similar data structures were discovered independently by Lueker, Lee and Wong, and Willard. The range tree is an alternative to the k-d tree. Compared to k-d trees, range trees offer faster query times of O(logd n + k) but worse storage of O(n logd−1 n), where n is the number of points stored in the tree, d is the dimension of each point and k is the number of points reported by a given query.
Read more about Range Tree: Description, See Also
Famous quotes containing the words range and/or tree:
“In the range of things toddlers have to learn and endlessly review—why you can’t put bottles with certain labels in your mouth, why you have to sit on the potty, why you can’t take whatever you want in the store, why you don’t hit your friends—by the time we got to why you can’t drop your peas, well, I was dropping a few myself.”
—Mary Kay Blakely (20th century)
“The wind flapped loose, the wind was still,
Shaken out dead from tree and hill:
I had walked on at the wind’s will,—
I sat now, for the wind was still.”
—Dante Gabriel Rossetti (1828–1882)