Range tree

Range tree

Ein Bereichsbaum (engl.: range tree) ist eine Datenstruktur für das Speichern einer Menge von Punkten im k-dimensionalen reellen Raum 	\mathbb{R} ^k. Er wird in der Informatik im Bereich der algorithmischen Geometrie eingesetzt und unterstützt effizient orthogonale Bereichsanfragen.

Inhaltsverzeichnis

Anwendungsgebiet

Anwendung finden solche Datenstrukturen in Geoinformationssystemen. Hier werden sie verwendet, um geographische Objekte zu suchen. Geoinformationssysteme verwalten die räumlichen Koordinaten dieser Objekte. Der Bereichsbaum unterteilt (partitioniert) nun die Objekte abhängig von ihren Koordinaten in Teilmengen. Dadurch kann später die Suche nach einem bestimmten Objekt auf einen kleinen Bereich eingegrenzt und damit erheblich beschleunigt werden. Solche Datenstrukturen werden auch als Indexstruktur bezeichnet.

Mathematische Beschreibung

Im einfachsten Falle, also \mathbb{R} ^1 ist der eindimensionale Bereichsbaum T1 ein gewöhnlicher binärer Suchbaum. Allgemein ist der k-dimensionale Bereichsbaum Tk rekursiv definiert:

Seien {x1,x2,...,xk} die Koordinatenachsen des \mathbb{R} ^k

  • Konstruiere zunächst einen 1-dimensionalen Bereichsbaum T1 für die Koordinatenachse x1, d.h. für 1-dimensionale Punkte, die sich durch abschneiden der hinteren k-1 Koordinaten ergeben. Jedem Knoten ist ein Intervall zugeordnet, das sich von der kleinsten bis zur größten Zahl erstreckt, die im Teilbaum des Knotens gespeichert ist.
  • Konstruiere rekursiv für jeden inneren Knoten v des T1 jeweils einen (k-1)-dimensionalen Bereichsbaum T_v ^{k-1} aus den (k-1)-dimensionalen Punkten, die im Teilbaum mit v als Wurzel enthalten sind und sich durch Abschneiden der ersten Koordinate ergeben.
  • Verbinde Knoten v des T1 mit Hilfe eines Zeigers mit dem zugehörigen T_v ^{k-1}

Der so aufgebaute Bereichsbaum unterstützt orthogonale Bereichsanfragen in

O(n(logn)k − 1) Speicherplatz
O((logn)k + a) Zeit, wobei a die Größe der Antwort ist, d.h. die Anzahl der Punkte im Anfragerechteck. Durch Fractional Cascading kann die Anfragedauer zu : O((logn)k − 1 + a) verbessert werden.

Siehe auch

Quadtree, K-d-Baum, UB-Baum, R-Baum, Gridfile als Alternative

Literatur

  • Rolf Klein: Algorithmische Geometrie 2. Auflage. Springer-Verlag, Berlin Heidelberg 2005, ISBN 3-540-20956-5.

Wikimedia Foundation.

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

Schlagen Sie auch in anderen Wörterbüchern nach:

  • 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… …   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”