Bereichsbaum

Baumstruktur in der Geoinformatik

Ein Bereichsbaum (englisch 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 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   ist der eindimensionale Bereichsbaum   ein gewöhnlicher binärer Suchbaum. Allgemein ist der k-dimensionale Bereichsbaum   rekursiv definiert:

Seien { } die Koordinatenachsen des  

  • Konstruiere zunächst einen 1-dimensionalen Bereichsbaum   für die Koordinatenachse  , d. h. für 1-dimensionale Punkte, die sich durch Abschneiden der hinteren   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   des   jeweils einen  -dimensionalen Bereichsbaum   aus den  -dimensionalen Punkten, die im Teilbaum mit   als Wurzel enthalten sind und sich durch Abschneiden der ersten Koordinate ergeben.
  • Verbinde Knoten   des   mit Hilfe eines Zeigers mit dem zugehörigen  

Der so aufgebaute Bereichsbaum unterstützt orthogonale Bereichsanfragen in

  Speicherplatz
  Zeit, wobei   die Größe der Antwort ist, d. h. die Anzahl der Punkte im Anfragerechteck. Durch Fractional Cascading kann die Anfragedauer zu   verbessert werden.

Siehe auch

Bearbeiten

Literatur

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