Bereichsbaum

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

Anwendunggebiet

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 <math>\mathbb{R} ^1</math> ist der eindimensionale Bereichsbaum <math>T^1</math> ein gewöhnlicher binärer Suchbaum. Allgemein ist der k-dimensionale Bereichsbaum <math>T^k</math> rekursiv definiert:

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

• Konstruiere zunächst einen 1-dimensionalen Bereichsbaum <math>T ^1</math> für die Koordinatenachse <math>x_1</math>, d.h. für 1-dimensionale Punkte, die sich durch abschneiden der hinteren k-1 Koordinaten ergeben.
• Konstruiere rekursiv für jeden inneren Knoten <math>v</math> des <math>T ^1</math> jeweils einen (k-1)-dimensionalen Bereichsbaum <math>T_v ^{k-1}</math> aus den (k-1)-dimensionalen Punkten, die sich durch abschneiden der ersten Koordinate ergeben.
• Verbinde Knoten <math>v</math> des <math>T^1</math> mit Hilfe eines Zeigers mit dem zugehörigen <math>T_v ^{k-1}</math>

Der so aufgebaute Bereichsbaum unterstützt orthogonale Bereichsanfragen in

<math>O(n*log(n))</math> Speicherplatz

<math>O(log(n) ^k + a)</math> Zeit, wobei <math>a</math> die Größe der Antwort ist, d.h. die Anzahl der Punkte im Anfragerechteck.