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:
“A girl must allow others to share the responsibility for care, thus enabling others to care for her. She must learn how to care in ways appropriate to her age, her desires, and her needs; she then acts with authenticity. She must be allowed the freedom not to care; she then has access to a wide range of feelings and is able to care more fully.”
—Jeanne Elium (20th century)
“the scythers, Time and Death,
Helmed locusts, move upon the tree of breath;”
—Robert Lowell (1917–1977)