Range tree

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.

Anwendungsgebiet

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

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

Seien {x₁,x₂,...,x_k} die Koordinatenachsen des $\mathbb{R} ^k$

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

Der so aufgebaute Bereichsbaum unterstützt orthogonale Bereichsanfragen in

O(n(logn)^{k − 1}) Speicherplatz

O((logn)^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((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.