k-d-Baum

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

k-d-Bäume sind Spezialfälle von BSP-Bäumen, deren teilende Hyperebenen entlang der Achsen des Koordinatensystems ausgerichtet sind.

Er wurde von Jon Bentley eingeführt.