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:
“The ideal of the self-sufficient American family is a myth, dangerous because most families, especially affluent families, do in fact make use of a range of services to survive. Families needing one or another kind of help are not morally deficient; most families do need assistance at one time or another.”
—Joseph Featherstone (20th century)
“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)