Drzewo kd

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacji, wyszukiwania
Przykład podziału przestrzeni przez drzewo kd dla k=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

Drzewo kd (skrót od drzewa k-wymiarowego) – struktura danych używana do dzielenia przestrzeni. Drzewa kd są przydatne w tworzeniu struktur w niektórych zastosowaniach takich jak wyszukiwanie najbliższych sąsiadów lub znajdywanie punktów w prostokątnych obszarach (w czasie O(\sqrt{n} + k), gdzie n to całkowita liczba punktów, k - liczba znalezionych punktów).

Są wariantem drzew binarnych.

Idea działania[edytuj | edytuj kod]

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

Bibliografia[edytuj | edytuj kod]

  • 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.

Zobacz też[edytuj | edytuj kod]