Bereichsbaum

aus Wikipedia, der freien Enzyklopädie

Du hast neue Nachrichten (Unterschied zur vorletzten Version).

Ein Bereichsbaum 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. Eine andere Möglichkeit für orthogonale Bereichsanfragen bietet der k-d-Baum.

[Bearbeiten] Anwendungsgebiet

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.

[Bearbeiten] Mathematische Beschreibung

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

Seien { $x 1, x 2,..., x k$ } die Koordinatenachsen des $\mathbb{R} ^k$

Konstruiere zunächst einen 1-dimensionalen Bereichsbaum $T 1$ für die Koordinatenachse $x 1$ , d.h. für 1-dimensionale Punkte, die sich durch abschneiden der hinteren k-1 Koordinaten ergeben.
Konstruiere rekursiv für jeden inneren Knoten $v$ des $T 1$ 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 1$ mit Hilfe eines Zeigers mit dem zugehörigen $T_v ^{k-1}$