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:
“Culture is the suggestion, from certain best thoughts, that a man has a range of affinities through which he can modulate the violence of any master-tones that have a droning preponderance in his scale, and succor him against himself. Culture redresses this imbalance, puts him among equals and superiors, revives the delicious sense of sympathy, and warns him of the dangers of solitude and repulsion.”
—Ralph Waldo Emerson (1803–1882)
“A tree is beautiful, but what’s more, it has a right to life; like water, the sun and the stars, it is essential. Life on earth is inconceivable without trees. Forests create climate, climate influences peoples’ character, and so on and so forth. There can be neither civilization nor happiness if forests crash down under the axe, if the climate is harsh and severe, if people are also harsh and severe.... What a terrible future!”
—Anton Pavlovich Chekhov (1860–1904)