Drzewo kd (, drzewo k-wymiarowe) – struktura danych, będąca wariantem drzew binarnych, używana do dzielenia przestrzeni. Drzewa kd są przydatne do tworzenia struktur w niektórych zastosowaniach, takich jak wyszukiwanie najbliższych sąsiadów lub znajdowanie punktów w prostokątnych obszarach. Czasowa złożoność obliczeniowa tych zadań wynosi  gdzie  to całkowita liczba punktów,  – liczba znalezionych punktów.

Idea działania 
 Każdy węzeł wewnętrzny tworzy hiperpłaszczyznę podziału, która dzieli przestrzeń na dwie podprzestrzenie. Punkty po lewej stronie hiperpłaszczyzny reprezentują lewe poddrzewo zaczynające się w tym węźle, a prawe punkty – prawe poddrzewo. Kierunek hiperpłaszczyzny jest wybierany zgodnie z wektorem normalnym do niej. Przykładowo, jeżeli podział nastąpił prostopadle do osi  w punkcie  to wszystkie punkty z wartością mniejszą niż  należą do lewego poddrzewa, a większe do prawego.

Zobacz też 
 drzewo BVH
 drzewo ósemkowe
 R-drzewo

Bibliografia 
 

KD
Modelowanie (grafika komputerowa)