k-d-Baum

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

Ein k-dimensionaler Baum oder k-d-Baum ist ein un-balancierter Suchbaum zur Speicherung von Punkten aus dem \mathbb{R}^k. Er bietet ähnlich dem Bereichsbaum die Möglichkeit, orthogonale Bereichsanfragen durchzuführen. Die Anfragekomplexität ist zwar höher, dafür ist der Speicheraufwand O(kn) statt O(n(\log n)^{k-1}).

Definition[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 H_i(t) = (x_1, x_2, \ldots , x_{i-1}, t , x_{i+1}, \ldots , x_k) 1 \leq i \leq k die achsenparallele (k-1)-dimensionale Hyperebene an der Stelle t. Für die Wurzel teilt man die Punkte durch die Hyperebene H_1(t) in zwei möglichst gleich große Punktemengen und trägt das t in die Wurzel ein, links davon werden alle Punkte gespeichert, deren x_1 kleiner sind als t, rechts von der Wurzel alle größeren. Für den linken Kindknoten werden die Punkte wiederum durch eine neue Splitebene H_2(t) geteilt und das t in dem inneren Knoten gespeichert. Links davon werden alle Punkte gespeichert, deren x_2 kleiner als t 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 O(n (k+ \log n)) konstruieren. Orthogonale Bereichsanfragen lassen sich in O(n^{1-\frac{1}{k}}+a) beantworten, wobei a die Größe der Antwort bezeichnet. Der Speicherplatzbedarf für den Baum selbst liegt in O(k \cdot n).

Beispiel 2-d-Baum[Bearbeiten]

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

Siehe auch[Bearbeiten]

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

Literatur[Bearbeiten]

Weblinks[Bearbeiten]