K-d-Baum

Der k‍-d-Baum oder auch k-dimensionale-Baum ist ein 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 unabhängig von der Dimension $k$ $O(n)$ .

Definition

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 Sohn werden die Punkte wiederum durch eine neue Splitebene $H_{2}(t)$ geteilt und die 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\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(n)$ .

Beispiel 2-d-Baum

Siehe auch

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

Literatur

Rolf Klein: Algorithmische Geometrie 2. Auflage. Springer-Verlag, Berlin Heidelberg 2005, ISBN 3-540-20956-5.

Weblinks

Universität Osnabrück