Drzewo kd

Drzewo kd (Szablon:Ang., 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 $O(\sqrt{n}+k),$ gdzie $n$ to całkowita liczba punktów, $k$ – liczba znalezionych punktów.

Idea działania

Szablon:Fakt 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 $X$ w punkcie $x,$ to wszystkie punkty z wartością mniejszą niż $x$ należą do lewego poddrzewa, a większe do prawego. Szablon:Ramka

Zobacz też

• drzewo BVH
• drzewo ósemkowe
• R-drzewo

Bibliografia

• Szablon:Cytuj książkę