K-Dimensional Tree (KD-tree) to struktura danych służąca do organizowania punktów w wielowymiarowej przestrzeni poprzez jej hierarchiczny podział. Działa na zasadzie binarnego drzewa poszukiwań, w którym każdy węzeł niebędący liściem reprezentuje hiperpłaszczyznę dzielącą przestrzeń na dwa obszary na podstawie wybranego wymiaru. Konstrukcja drzewa polega na cyklicznym przechodzeniu przez kolejne wymiary i wybieraniu mediany jako punktu podziału, co pozwala na uzyskanie zrównoważonej struktury. Jest to rozwiązanie szczególnie przydatne w algorytmach wyszukiwania najbliższych sąsiadów oraz przeszukiwania zakresowego, ponieważ pozwala na szybkie odrzucanie dużych obszarów danych.
Źródło: geeksforgeeks.org
