www.wikidata.de-de.nina.az

Bereichsbaum Ein englisch range tree ist eine Datenstruktur für das Speichern einer Menge von Punkten im k dimensionalen

Bereichsbaum

Ein Bereichsbaum (englisch 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 orthogonale Bereichsanfragen.

Anwendungsgebiet Bearbeiten

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 Bearbeiten

Im einfachsten Falle, also ist der eindimensionale Bereichsbaum ein gewöhnlicher binärer Suchbaum. Allgemein ist der k-dimensionale Bereichsbaum rekursiv definiert:

Seien {} die Koordinatenachsen des

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

Der so aufgebaute Bereichsbaum unterstützt orthogonale Bereichsanfragen in

Siehe auch Bearbeiten

Literatur Bearbeiten

  • Rolf Klein: Algorithmische Geometrie 2. Auflage. Springer-Verlag, Berlin Heidelberg 2005, ISBN 3-540-20956-5.
wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele
Veröffentlichungsdatum:
Ein Bereichsbaum englisch range tree ist eine Datenstruktur fur das Speichern einer Menge von Punkten im k dimensionalen reellen Raum R k displaystyle mathbb R k Er wird in der Informatik im Bereich der algorithmischen Geometrie eingesetzt und unterstutzt effizient orthogonale Bereichsanfragen Inhaltsverzeichnis 1 Anwendungsgebiet 2 Mathematische Beschreibung 3 Siehe auch 4 LiteraturAnwendungsgebiet BearbeitenAnwendung finden solche Datenstrukturen in Geoinformationssystemen Hier werden sie verwendet um geographische Objekte zu suchen Geoinformationssysteme verwalten die raumlichen Koordinaten dieser Objekte Der Bereichsbaum unterteilt partitioniert nun die Objekte abhangig von ihren Koordinaten in Teilmengen Dadurch kann spater 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 BearbeitenIm einfachsten Falle also R 1 displaystyle mathbb R 1 nbsp ist der eindimensionale Bereichsbaum T 1 displaystyle T 1 nbsp ein gewohnlicher binarer Suchbaum Allgemein ist der k dimensionale Bereichsbaum T k displaystyle T k nbsp rekursiv definiert Seien x 1 x 2 x k displaystyle x 1 x 2 dotsc x k nbsp die Koordinatenachsen des R k displaystyle mathbb R k nbsp Konstruiere zunachst einen 1 dimensionalen Bereichsbaum T 1 displaystyle T 1 nbsp fur die Koordinatenachse x 1 displaystyle x 1 nbsp d h fur 1 dimensionale Punkte die sich durch Abschneiden der hinteren k 1 displaystyle k 1 nbsp Koordinaten ergeben Jedem Knoten ist ein Intervall zugeordnet das sich von der kleinsten bis zur grossten Zahl erstreckt die im Teilbaum des Knotens gespeichert ist Konstruiere rekursiv fur jeden inneren Knoten v displaystyle v nbsp des T 1 displaystyle T 1 nbsp jeweils einen k 1 displaystyle k 1 nbsp dimensionalen Bereichsbaum T v k 1 displaystyle T v k 1 nbsp aus den k 1 displaystyle k 1 nbsp dimensionalen Punkten die im Teilbaum mit v displaystyle v nbsp als Wurzel enthalten sind und sich durch Abschneiden der ersten Koordinate ergeben Verbinde Knoten v displaystyle v nbsp des T 1 displaystyle T 1 nbsp mit Hilfe eines Zeigers mit dem zugehorigen T v k 1 displaystyle T v k 1 nbsp Der so aufgebaute Bereichsbaum unterstutzt orthogonale Bereichsanfragen in O n log n k 1 displaystyle O n log n k 1 nbsp Speicherplatz O log n k a displaystyle O log n k a nbsp Zeit wobei a displaystyle a nbsp die Grosse der Antwort ist d h die Anzahl der Punkte im Anfragerechteck Durch Fractional Cascading kann die Anfragedauer zu O log n k 1 a displaystyle O log n k 1 a nbsp verbessert werden Siehe auch BearbeitenQuadtree K d Baum UB Baum R Baum Gridfile als AlternativeLiteratur BearbeitenRolf Klein Algorithmische Geometrie 2 Auflage Springer Verlag Berlin Heidelberg 2005 ISBN 3 540 20956 5 Abgerufen von https de wikipedia org w index php title Bereichsbaum amp oldid 159209912