Drzewo kd

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

Idea działania

Drzewo kd jest drzewem binarnym, w którym w każdym węźle zewnętrznym znajduje się k-wymiarowy punkt. 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.

Przykład podziału przestrzeni przez drzewo kd dla k równego 3. Pierwszy podział (czerwony) dzieli główną komórkę (biała) na dwie podkomórki. Każda z nich jest następnie dzielona (zielona) na kolejne podkomórki. Ostatecznie dzielona jest na niebieskie komórki. Gdy już nie można dalej dzielić, każda z ośmiu komórek jest liściem, tj. elementem, który dalej nie podlega rozgałęzieniom.

Zobacz też

• drzewo BVH
• drzewo ósemkowe
• R-drzewo

Bibliografia

• Kd-drzewa. W: Mark de Berg, Mirosław Kowaluk: Geometria obliczeniowa. Algorytmy i zastosowania. Warszawa: Wydawnictwa Naukowo-Techniczne, 2007, s. 118–125. ISBN 978-83-204-3244-2.