Back K-d tree English Árbol kd Spanish درخت کیدی Persian Arbre kd French עץ kd HE Kd木 Japanese K-d 트리 Korean Drzewo kd Polish Árvore k-d Portuguese K-d-дерево Russian
Ein Quader wird von zweidimensionalen Hyperebenen in dreidimensionale Punktemengen (Teilquader) geteilt. Die erste Hyperebene (die rot umrandete vertikale Ebene) schneidet den Quader (weiß umrandet) in 2 Punktemengen, von denen jede dann von den grün umrandeten horizontalen Hyperebenen in 2 Teilquader geteilt wird. Schließlich werden die 4 Teilquader von den 4 blau umrandeten vertikalen Hyperebenen in jeweils 2 Teilquader geteilt. Insgesamt entstehen also 8 Teilquader.
Ein -dimensionaler Baum oder -d-Baum ist ein balancierter 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 liegt der Speicheraufwand in statt in (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.