Drzewo kd


Drzewo kd w encyklopedii

Z Wikipedii, wolnej encyklopedii Przejdź do nawigacji Przejdź do wyszukiwania

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

Idea działania | edytuj kod

Drzewo 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 X {\displaystyle X} w punkcie x , {\displaystyle x,} to wszystkie punkty z wartością mniejszą niż x {\displaystyle 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ż | edytuj kod

Bibliografia | 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.
Na podstawie artykułu: "Drzewo kd" pochodzącego z Wikipedii
OryginałEdytujHistoria i autorzy