Bereichsbaum

Ein Bereichsbaum (englisch 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. 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 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(n(log n)k − 1) Speicherplatz
O((log n)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((log n)k − 1 + a) verbessert werden.

Siehe auch

Literatur

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

Wikimedia Foundation.

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Range tree — Ein Bereichsbaum (engl.: 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… …   Deutsch Wikipedia

  • K-d-Baum — Ein k dimensionaler Baum oder k d Baum ist ein balancierter Suchbaum zur Speicherung von Punkten aus dem . Er bietet ähnlich dem Bereichsbaum die Möglichkeit, orthogonale Bereichsanfragen durchzuführen. Die Anfragekomplexität ist zwar höher,… …   Deutsch Wikipedia

  • Kd-Baum — Ein k dimensionaler Baum oder k d Baum ist ein balancierter Suchbaum zur Speicherung von Punkten aus dem . Er bietet ähnlich dem Bereichsbaum die Möglichkeit, orthogonale Bereichsanfragen durchzuführen. Die Anfragekomplexität ist zwar höher,… …   Deutsch Wikipedia

  • Kd-Tree — Ein k dimensionaler Baum oder k d Baum ist ein balancierter Suchbaum zur Speicherung von Punkten aus dem . Er bietet ähnlich dem Bereichsbaum die Möglichkeit, orthogonale Bereichsanfragen durchzuführen. Die Anfragekomplexität ist zwar höher,… …   Deutsch Wikipedia

  • R*-Baum — Ein Beispiel eines R Baums Ein R Baum (eng. R tree) ist eine in Datenbanksystemen verwendete räumliche (man sagt auch mehrdimensionale) Indexstruktur. Inhaltsverzeichnis 1 Verwendungszweck 2 …   Deutsch Wikipedia

  • R-tree — Ein Beispiel eines R Baums Ein R Baum (eng. R tree) ist eine in Datenbanksystemen verwendete räumliche (man sagt auch mehrdimensionale) Indexstruktur. Inhaltsverzeichnis 1 Verwendungszweck 2 …   Deutsch Wikipedia

  • Rtree — Ein Beispiel eines R Baums Ein R Baum (eng. R tree) ist eine in Datenbanksystemen verwendete räumliche (man sagt auch mehrdimensionale) Indexstruktur. Inhaltsverzeichnis 1 Verwendungszweck 2 …   Deutsch Wikipedia

  • Universal B-Tree — Der UB Baum („Universal B Tree“) wurde von Rudolf Bayer und Volker Markl vorgeschlagen und ist eine Datenstruktur für mehrdimensionale Datenbanksysteme. Es ist ein B+ Baum, bei dem die Daten nach der Z Kurve (Berechnen der Z Werte durch bitweise… …   Deutsch Wikipedia

  • k-d-Baum — Ein k dimensionaler Baum oder k d Baum ist ein un balancierter Suchbaum zur Speicherung von Punkten aus dem . Er bietet ähnlich dem Bereichsbaum die Möglichkeit, orthogonale Bereichsanfragen durchzuführen. Die Anfragekomplexität ist zwar höher,… …   Deutsch Wikipedia

  • Fractional Cascading — bietet die Möglichkeit, die Bereichssuche in einem Bereichsbaum schneller zu gestalten. Dabei wird der jeweils höchstdimensionale assoziierte Baum nicht als Baum, sondern als Array gespeichert. Von jedem Element des Arrays gehen Verweise auf… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”