Quaternärbaum

aus Wikipedia, der freien Enzyklopädie
(Weitergeleitet von Quadtree)
Wechseln zu: Navigation, Suche
Ein Punktequaternärbaum mit Punktdaten. Behälterkapazität: 1.
Quaternärbaumkompression eines Bildes, Schritt für Schritt

Ein Quaternärbaum ist in der Informatik eine Baumstruktur, in der jeder innere Knoten genau vier Tochterknoten hat. Quaternärbäume werden hauptsächlich zur Unterteilung eines zweidimensionalen Raumes genutzt, indem rekursiv in vier Bereiche (Quadranten) unterteilt wird. Die Bereiche können quadratisch oder rechteckig sein oder beliebige Formen haben. Eine ähnliche Aufteilung ist als Q-tree bekannt. Alle Formen von Quaternärbäumen teilen bestimmte Merkmale:

  • Sie zerlegen den Raum in anpassbare Bereiche
  • Jeder Bereich hat eine Maximalkapazität. Wird diese erreicht, so wird der Bereich unterteilt.
  • Das Baumverzeichnis folgt der räumlichen Unterteilung des Quaternärbaumes.

Arten[Bearbeiten | Quelltext bearbeiten]

Quaternärbäume können nach der Art der von ihnen repräsentierten Daten eingeteilt werden, einschließlich Flächen, Punkten und Linien. Quaternärbäume können auch danach eingeteilt werden, ob die Form des Baumes von der Datenverarbeitungsreihenfolge abhängt oder nicht. Einige gebräuchliche Arten von Quaternärbäumen sind:

Der Bereichsquaternärbaum[Bearbeiten | Quelltext bearbeiten]

Der Bereichsquaternärbaum stellt eine Aufteilung des Raums in zwei Dimensionen dar, der den Bereich in vier gleiche Quadranten, Unterquadranten usw. zerlegt, wobei jeder Endknoten Daten eines bestimmten Unterbereiches enthält. Jeder Knoten in dem Baum hat entweder genau vier Kinder oder gar keine (Blattknoten). Der Bereichsquaternärbaum ist eine Art von Trie.

Ein Bereichsquaternärbaum mit einer Tiefe von n kann benutzt werden um ein Bild aus 2n × 2n Bildpunkten darzustellen, wobei jeder Bildpunkt den Wert 1 oder 0 hat. Der Wurzelknoten repräsentiert den gesamten Bildbereich. Sofern in einem Bereich nicht alle Bildpunkte Nullen oder Einsen sind, wird dieser unterteilt. In dieser Anwendung steht jeder Endknoten für einen Bildbereich, dessen Bildpunkte sämtlich Nullen oder Einsen sind.

Ein Bereichsquaternärbaum kann auch als eine variabel aufgelöste Repräsentation eines Datenfeldes genutzt werden. Beispielsweise können die Temperaturen in einem Gebiet als Quaternärbaum gespeichert werden, wobei in jedem Blatt die Durchschnittstemperatur des Teilgebietes gespeichert wird.

Wenn ein Bereichsquaternärbaum benutzt wird, um einen Punktdatensatz zu repräsentieren (zum Beispiel Längen- und Breitengrade einer Anzahl von Städten), so werden Bereiche so oft unterteilt, bis jedes Blatt höchstens einen Punkt enthält.

Punktquaternärbaum[Bearbeiten | Quelltext bearbeiten]

Der Punktquaternärbaum ist eine Anpassung eines Binärbaumes, die zur Darstellung zweidimensionaler Punktdaten genutzt wird. Es teilt die Merkmale eines Quaternärbaumes, ist allerdings ein echter Baum, da das Zentrum einer Unterteilung immer ein Punkt ist. Die Form des Baumes hängt von der Reihenfolge der Datenverarbeitung ab. Er ist mit einer Ausführungszeit von üblicherweise O(log n) oft sehr effizient beim Vergleichen zweidimensionaler, sortierter Datenpunkte.

Knotenstruktur eines Punktquaternärbaumes[Bearbeiten | Quelltext bearbeiten]

Ein Knoten eines Punktquaternärbaumes ähnelt einem Knoten eines Binärbaumes, von dem er sich hauptsächlich durch die vier Zeiger (einer pro Quadrant) von den zwei Zeigern (links und rechts) eines gewöhnlichen Binärbaumes unterscheidet. Zusätzlich ist ein Schlüssel gewöhnlich in zwei Komponenten gegliedert, die sich auf die x- und die y-Koordinaten beziehen. Daher enthält ein Knoten die folgende Information:

  • vier Zeiger: quad[‘NW’], quad[‘NO’], quad[‘SW’] und quad[‘SO’]
  • Punkt, welcher wiederum enthält:
    • Attribut, gewöhnlich als x- und y-Koordinaten ausgedrückt
    • Wert, beispielsweise ein Name

Kantenquaternärbaum[Bearbeiten | Quelltext bearbeiten]

Kantenquaternärbäume werden besonders zur Speicherung von Linien statt Punkten genutzt. Kurven werden durch fein aufgelöste Unterteilung von Zellen angenähert. Dies kann zu sehr unausgewogenen Bäumen führen, was dem Zweck der Indizierung zuwiderlaufen kann.

Einige gebräuchliche Nutzungen von Quaternärbäumen[Bearbeiten | Quelltext bearbeiten]

Quaternärbäume sind die zweidimensionale Entsprechung zu Oktonärbäumen.

Einzelnachweise[Bearbeiten | Quelltext bearbeiten]

  1. Tomas G. Rokicki: An Algorithm for Compressing Space and Time. 1. April 2006. Abgerufen am 20. Mai 2009.
  2. Henning Eberhardt, Vesa Klumpp, Uwe D. Hanebeck, Density Trees for Efficient Nonlinear State Estimation. Proceedings of the 13th International Conference on Information Fusion, Edinburgh, United Kingdom, Juli 2010.

Literatur[Bearbeiten | Quelltext bearbeiten]

  • Hanan Samet: The Design and Analysis of Spatial Data Structures. Addison-Wesley, Reading, MA, 1990, ISBN 0-201-50255-0.
  • Hanan Samet: Applications of Spatial Data Structures: Computer Graphics, Image Processing, and GIS. Addison-Wesley, Reading, MA, 1990, ISBN 0-201-50300-X.
  • R. A. Finkel, J. L. Bentley: Quad trees a data structure for retrieval on composite keys. In: Acta Informatica. Band 4, Nr. 1, ISSN 0001-5903, S. 1–9, doi:10.1007/BF00288933.
  • Mark de Berg, Marc van Kreveld, Mark Overmars, Otfried Schwarzkopf (Hrsg.): Computational Geometry. Algorithms and applications. 2., rev. Auflage. Springer, Berlin u. a. 2000, ISBN 3-540-65620-0, 14: Quadtrees, S. 291–306.
  • Hanan Samet, Robert Webber: Storing a Collection of Polygons Using Quadtrees. Juli 1985, abgerufen am 23. März 2012 (PDF).

Weblinks[Bearbeiten | Quelltext bearbeiten]

 Commons: Quadtrees – Sammlung von Bildern, Videos und Audiodateien

Implementierungen