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:
“For generations, a wide range of shooting in Northern Ireland has provided all sections of the population with a pastime which ... has occupied a great deal of leisure time. Unlike many other countries, the outstanding characteristic of the sport has been that it was not confined to any one class.”
—Northern Irish Tourist Board. quoted in New Statesman (London, Aug. 29, 1969)
“What signify a few lives lost in a century or two? The tree of liberty must be refreshed from time to time with the blood of patriots and tyrants. It is its natural manure.”
—Thomas Jefferson (1743–1826)