Bereichsbaum

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

Ein Bereichsbaum (englisch 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.

Anwendungsgebiet[Bearbeiten]

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[Bearbeiten]

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

Seien {x_1, x_2, ... , x_k} die Koordinatenachsen des \mathbb{R} ^k

  • Konstruiere zunächst einen 1-dimensionalen Bereichsbaum T ^1 für die Koordinatenachse x_1, 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 T ^1 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 T^1 mit Hilfe eines Zeigers mit dem zugehörigen T_v ^{k-1}

Der so aufgebaute Bereichsbaum unterstützt orthogonale Bereichsanfragen in

O(n (\log n)^{k-1}) Speicherplatz
O((\log n)^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((\log n)^{k-1} + a) verbessert werden.

Siehe auch[Bearbeiten]

Literatur[Bearbeiten]

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