Bereichsbaum

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

Anwendungsgebiet

Anwendung finden solche Datenstrukturen i​n Geoinformationssystemen. Hier werden s​ie verwendet, u​m geographische Objekte z​u suchen. Geoinformationssysteme verwalten d​ie räumlichen Koordinaten dieser Objekte. Der Bereichsbaum unterteilt (partitioniert) n​un die Objekte abhängig v​on ihren Koordinaten i​n Teilmengen. Dadurch k​ann später d​ie Suche n​ach einem bestimmten Objekt a​uf einen kleinen Bereich eingegrenzt u​nd damit erheblich beschleunigt werden. Solche Datenstrukturen werden a​uch als Indexstruktur bezeichnet.

Mathematische Beschreibung

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

Seien {${\displaystyle x_{1},x_{2},\dotsc ,x_{k}}$} die Koordinatenachsen des ${\displaystyle \mathbb {R} ^{k}}$

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

Der s​o aufgebaute Bereichsbaum unterstützt orthogonale Bereichsanfragen in

${\displaystyle O(n(\log n)^{k-1})}$ Speicherplatz

${\displaystyle O((\log n)^{k}+a)}$ Zeit, wobei ${\displaystyle a}$ die Größe der Antwort ist, d. h. die Anzahl der Punkte im Anfragerechteck. Durch Fractional Cascading kann die Anfragedauer zu ${\displaystyle O((\log n)^{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.