Range tree

Range tree

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 efficiently retrieved, and is typically used in two or higher dimensions.

It is similar to a kd-tree except with faster query times of O(log2 "n" + "k") but worse storage of O("n" log "n"), with "n" being the number of points in the tree, and "k" being the number of points retrieved for a given query.

Range trees may be contrasted with interval trees: instead of storing points and allowing points in a given range to be retrieved efficiently, it stores intervals and allows the intervals containing a given point to be retrieved efficiently.

References

* Mark de Berg, Marc van Kreveld, Mark Overmars, and Otfried Schwarzkopf. "Computational Geometry", Second Revised Edition. Springer-Verlag 2000. Section 5.3: Range Trees, pp.105-110.


Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать реферат

Look at other dictionaries:

  • Range tree — Ein Bereichsbaum (engl.: range tree) ist eine Datenstruktur für das Speichern einer Menge von Punkten im k dimensionalen reellen Raum . Er wird in der Informatik im Bereich der algorithmischen Geometrie eingesetzt und unterstützt effizient… …   Deutsch Wikipedia

  • Tree (data structure) — A simple unordered tree; in this diagram, the node labeled 7 has two children, labeled 2 and 6, and one parent, labeled 2. The root node, at the top, has no parent. In computer science, a tree is a widely used data structure that emulates a… …   Wikipedia

  • Tree — /tree/, n. Sir Herbert Beerbohm /bear bohm/, (Herbert Beerbohm), 1853 1917, English actor and theater manager; brother of Max Beerbohm. * * * I Woody perennial plant. Most trees have a single self supporting trunk containing woody tissues, and in …   Universalium

  • Tree Pangolin — Tree Pangolin[1] Conservation status …   Wikipedia

  • Tree sitting — is a form of environmentalist civil disobedience in which a protester sits in a tree, usually on a small platform built for the purpose, to protect it from being cut down (speculating that loggers will not endanger human lives by cutting an… …   Wikipedia

  • Tree house — Tree houses, treehouses, or tree forts, are buildings constructed among the branches, around or next to the trunk of one or more mature trees, and are raised above the ground. Tree houses are built and used for recreation, as temporary retreats,… …   Wikipedia

  • Tree breeding — is the application of genetic principles to the genetic improvement and management of forest trees. In contrast to the selective breeding of livestock, arable crops, and horticultural flowers over the last few centuries, the breeding of trees,… …   Wikipedia

  • tree — treelike, adj. /tree/, n., v., treed, treeing. n. 1. a plant having a permanently woody main stem or trunk, ordinarily growing to a considerable height, and usually developing branches at some distance from the ground. 2. any of various shrubs,… …   Universalium

  • Tree of Life (Judeo-Christian) — See also Tree of life for other cultural interpretations of the term, and : Tree of life (disambiguation) for other meanings of the term. The Tree of Life (Heb. עץ החיים Etz haChayim ), in the Book of Genesis is a tree planted by God in midst of… …   Wikipedia

  • Tree hollow — A tree hollow or tree hole is a semi enclosed cavity which has naturally formed in the trunk or branch of a tree. These are predominantly found in old trees, whether living or not. Hollows form in many species of trees, and are a prominent… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”