Das Kefk Network Wiki befindet sich im Testbetrieb.

Bereichsbaum

Aus Kefk.

Wechseln zu: Navigation, Suche

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. Geoinformstionssysteme verwalten die räumlichen Koordinaten dieser Objekte. Der Bereichsbaum unterteilt (partitioniert) nun die Objekte abhängig von ihren Koordindaten 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(nlogn) Speicherplatz
O((logn)k + a) Zeit, wobei a die Größe der Antwort ist, d.h. die Anzahl der Punkte im Anfragerechteck. Durch sogenanntes 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.
Von „http://www.kefk.org/wiki/Bereichsbaum“
Persönliche Werkzeuge