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 gdzie to całkowita liczba punktów, – liczba znalezionych punktów.
Idea działania
edytujDrzewo kd jest drzewem binarnym, w którym w każdym węźle zewnętrznym znajduje się k-wymiarowy punkt.[potrzebny przypis] 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ż
edytujBibliografia
edytuj- 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.