k-d-Baum

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

Ein -dimensionaler Baum oder -d-Baum ist ein unbalancierter 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, dafür ist der Speicheraufwand statt .

k-d-Bäume sind Spezialfälle von BSP-Bäumen.

Definition[Bearbeiten | Quelltext bearbeiten]

Es gibt homogene und inhomogene k-d-Bäume. Bei homogenen k-d-Bäumen speichert jeder Knoten einen Datensatz. Bei der inhomogenen Variante enthalten die inneren Knoten lediglich Schlüssel, die Blätter enthalten Verweise auf Datensätze.

Bei einem inhomogenen k-d-Baum sei die achsenparallele -dimensionale Hyperebene an der Stelle . Für die Wurzel teilt man die Punkte durch die Hyperebene in zwei möglichst gleich große Punktemengen und trägt das in die Wurzel ein, links davon werden alle Punkte gespeichert, deren kleiner sind als , rechts von der Wurzel alle größeren. Für den linken Kindknoten werden die Punkte wiederum durch eine neue Splitebene geteilt und das in dem inneren Knoten gespeichert. Links davon werden alle Punkte gespeichert, deren kleiner als ist. Dies wird nun rekursiv über alle Dimensionen fortgeführt. Danach wird wieder bei der ersten Dimension angefangen, bis jeder Punkt durch Hyperebenen eindeutig identifiziert werden kann.

Ein k-d-Baum lässt sich in konstruieren. Orthogonale Bereichsanfragen lassen sich in beantworten, wobei die Größe der Antwort bezeichnet. Der Speicherplatzbedarf für den Baum selbst liegt in .

Beispiel 2-d-Baum[Bearbeiten | Quelltext bearbeiten]

Eine Menge von Punkten mit dazugehörigem inhomogenem 2-d-Baum

Siehe auch[Bearbeiten | Quelltext bearbeiten]

Quadtree, Octree, UB-Baum, R-Baum, Bereichsbaum, Gridfile als Alternativen.

Literatur[Bearbeiten | Quelltext bearbeiten]

Weblinks[Bearbeiten | Quelltext bearbeiten]