Kd-Tree

Ein k-dimensionaler Baum oder k-d-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 O(kn) statt O(n(logn)^{k − 1}) .

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₁(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₁ 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₂(t) geteilt und das t in dem inneren Knoten gespeichert. Links davon werden alle Punkte gespeichert, deren x₂ 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(nlogn) 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

• J. L. Bentley: Multidimensional binary search trees used for associative searching. Communications of the ACM 18, 9 (September 1975), S. 509–517
• J. L. Bentley: K-d Trees for Semidynamic Point Sets. SCG '90: Proceedings of the 6th Annual Symposium on Computational Geometry, 1990, S. 187–197
• Rolf Klein: Algorithmische Geometrie, 2. Auflage. Springer-Verlag, Berlin Heidelberg 2005, ISBN 3-540-20956-5

Weblinks

• Universität Osnabrück: k-d-Baum