Kd-tree

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 23 iulie 2021; verificările necesită 2 modificări .

Arborele K-dimensional

Tip de

Arborele multidimensional Arborele de căutare binar

Anul inventiei

1975

Autor

Jon Bentley

Complexitatea în simbolurile O

	In medie	În cel mai rău caz
Consumul de memorie	O( n )	O( n )
Căutare	O( login )	O( n )
Introduce	O( login )	O( n )
Îndepărtarea	O( login )	O( n )

Un k -d-tree ( eng. kd tree , prescurtare pentru arbore k-dimensional ) este o structură de date partiționată în spațiu pentru ordonarea punctelor într-un spațiu k - dimensional. k -d-arborele sunt utilizați pentru unele aplicații, cum ar fi căutarea multidimensională cu spațiu de taste (căutare în interval și căutare în cel mai apropiat vecin ). k -d-trees sunt un tip special de arbori binari de căutare .

Descriere matematică

Un arbore K-dimensional este un arbore de căutare dezechilibrat pentru stocarea punctelor din . Oferă o capacitate asemănătoare arborelui R de a căuta într-un interval dat de taste. În detrimentul simplității interogărilor, cerințele de memorie în loc de . ${\mathbb {R}}^{k}$ $O(kn)$ $O((log(n))^{k-1})$

Există arbori kd omogene și neomogene. În arborii kd omogene, fiecare nod stochează o înregistrare . În varianta eterogenă, nodurile interne conțin doar chei, frunzele conțin link-uri către înregistrări.

Într-un arbore kd neomogen cu un hiperplan -dimensional paralel cu axa în punctul . Pentru rădăcină, trebuie să împărțiți punctele prin hiperplan în două seturi de puncte cât mai mari posibil și să scrieți la rădăcină, în stânga acesteia, toate punctele pentru care sunt stocate , la dreapta, cele pentru care . Pentru subarborele din stânga trebuie să împărțiți din nou punctele într-un nou „plan divizat” și este stocat în nodul intern. În stânga acestuia, toate punctele pentru care . Aceasta continuă recursiv pe toate spațiile. Apoi totul începe din nou din primul spațiu până când fiecare punct poate fi identificat clar prin hiperplan. $H_{i}(t)=(x_{1},x_{2},\ldots,x_{i-1},t,x_{i+1},\ldots,x_{k})$ $1\leq i\leq k$ $(k-1)$ $t$ $H_{1}(t)$ $t$ $x_{1}<t$ $x_{1}>t$ $H_{2}(t)$ $t$ $x_{2}<t$

arborele kd poate fi construit în . O căutare în intervalul poate fi efectuată în , prin care indică dimensiunea răspunsului. Necesarul de memorie pentru arborele în sine este limitat . $O(n(k+log(n)))$ $O(n^{1-{\frac {1}{k}}}+a)$ $A$ $O(kn)$

Operații pe k -d-arbori

Structura

Structura arborescentă descrisă în C++ :

amprenta constex N = 10 ; _ // numărul de spații de taste struct Item { // item structure int key [ N ]; // matrice de chei care definesc elementul char * info ; // informații despre element }; struct Node { // structura nodului arborescent Item i ; // element Node * stânga ; // subarborele stânga Nod * dreapta ; // subarborele din dreapta }

Structura arborelui poate varia în funcție de detaliile implementării algoritmului . De exemplu, un nod poate conține mai degrabă o matrice decât un singur element, ceea ce îmbunătățește eficiența căutării.

Analiza Căutării Elementelor

Evident, numărul minim de elemente vizualizate este , iar numărul maxim de elemente vizualizate este , unde este înălțimea arborelui. Rămâne de calculat numărul mediu de articole vizualizate . $unu$ $Oh)$ $h$ $Un}$

$[x_{0},x_{1},x_{2},...,x_{n}]$ este elementul dat.

Să luăm în considerare cazul . Elementele găsite pot fi: $h=3$

find(t_{1}):[(x_{0}=t_{1})];A=1.

find(t_{2}):[(x_{0}<t_{1})\land (x_{0}=t_{2})];A=2.

find(t_{3}):[(x_{0}>t_{1})\land (x_{0}=t_{3})];A=2.

find(t_{4}):[(x_{0}<t_{1})\land (x_{0}<t_{2})\land (x_{0}=t_{4})] ;A=3.

find(t_{5}):[(x_{0}<X_{1})\land (x_{0}>t_{2})\land (x_{0}=t_{5})] ;A=3.

find(t_{6}):[(x_{0}<t_{1})\land (x_{0}<t_{3})\land (x_{0}=t_{6})] ;A=3.

find(t_{7}):[(x_{0}<t_{1})\land (x_{0}>t_{3})\land (x_{0}=t_{7})] ;A=3.

și așa mai departe pentru fiecare spațiu de taste. În acest caz, lungimea medie a căutării într-un spațiu este:

A={\frac {1+2+2+3+3+3+3}{7}}={\frac {17}{7}}\aproximativ 2,4

Valoarea medie se calculează cu formula: $A_{n}=\sum _{k=1}^{n}kp_{n,k)$

Rămâne de găsit probabilitatea . Este egal cu , unde este numărul de cazuri, când și este numărul total de cazuri. Nu este greu de ghicit ce . $p_{n,k)$ $p_{n,k}={\frac {p_{A,k}}{p_{n}))$ $p_{A,k)$ $A=k$ $p_{n}$ $p_{n,k}={\frac {2^{k-1}}{2^{n}-1}}$

Inlocuim aceasta in formula pentru valoarea medie:

A_{n}=\sum _{k=1}^{n}kp_{n,k}=\sum _{k=1}^{n}{k{\frac {2^{k- 1}}{2^{n}-1}}}={\frac {1}{2^{n}-1}}\sum _{k=1}^{n}{k2^{k-1 }}=

={\frac {1}{2^{n}-1}}\sum _{k+1=1}^{n}{({k+1})2^{k}}={ \frac {1}{2^{n}-1}}\left(\sum _{k+1=1}^{n}{k2^{k}}+\sum _{k+1=1} ^{n}{2^{k}}\dreapta)=

={\frac {1}{2^{n}-1}}\left(\sum _{k=1}^{n}{k2^{k}}+\sum _{k=1 }^{n}{2^{k}}-2^{n}-n2^{n}\right)=

={\frac {1}{2^{n}-1}}(n2^{n+2}-(n+1)2^{n+1}+2-2^{n}+ 2^{3}-1-n2^{n})={\frac {2^{n}(n-1)+1}{2^{n}-1))

adică unde este înălțimea copacului. $A_{h}={\frac {2^{h}(h-1)+1}{2^{h}-1))$ $h$

Dacă mergem de la înălțimea arborelui la numărul de elemente, atunci:

A_{n}=~O\left({\frac {2^{h}(h-1)+1}{2^{h}-1}}\right)=~O\left(h {\frac {2^{h}}{2^{h}-1}}-1\right)=~O\left(log\left({\frac {n}{N}}+1\right) {\frac {2^{log\stânga({\frac {n}{N}}+1\dreapta))){2^{log\left({\frac {n}{N}}+1\dreapta) )}-1}}-1\right)=~O\left(log\left({\frac {n}{N}}+1\right){\frac {n+N}{n}}-1 \dreapta)=

$=~O\left(log\left({\frac {n}{N}}+1\right)^{\frac {n+N}{n}}-1\right)$ , unde este numărul de elemente din nod. $N$

Din aceasta putem concluziona că cu cât vor fi conținute mai multe elemente în nod, cu atât căutarea arborelui va fi mai rapidă, deoarece înălțimea arborelui va rămâne minimă, dar nu ar trebui să stocați un număr mare de elemente în nod, deoarece cu această metodă întregul arbore poate degenera într-o matrice sau listă normală.

Adăugarea elementelor

Adăugarea elementelor are loc exact în același mod ca într-un arbore de căutare binar normal , cu singura diferență că fiecare nivel al arborelui va fi determinat și de spațiul căruia îi aparține.

Algoritm de progresie a arborelui:

pentru ( int i = 0 ; arbore ; i ++ ) // i este numărul spațiului dacă ( arbore -> x [ i ] < arbore -> t ) // t este arborele median = arbore -> stânga ; // trece la subarborele din stânga altfel copac = copac -> dreapta ; // se deplasează în subarborele din dreapta

Adăugarea se efectuează după , unde este înălțimea arborelui. $Oh)$ $h$

Eliminarea elementelor

La ștergerea elementelor arborelui, pot apărea mai multe situații:

Ștergerea unei frunze de copac este o ștergere destul de simplă, atunci când un nod este șters și indicatorul nodului strămoș este pur și simplu resetat la zero.

Eliminarea unui nod de arbore (nu a unei frunze) este o procedură foarte complicată, în care trebuie să reconstruiți întregul subarboresc pentru acest nod.

Uneori, procesul de ștergere a unui nod este rezolvat prin modificarea arborelui kd. De exemplu, dacă nodul nostru conține o matrice de elemente, atunci când întregul tablou este șters, nodul arborelui rămâne, dar elemente noi nu mai sunt scrise acolo.

Găsirea unei game de elemente

Căutarea se bazează pe coborârea normală a arborelui, unde fiecare nod este verificat pentru un interval. Dacă medianele unui nod sunt mai mici sau mai mari decât un interval dat într-un spațiu dat, atunci traversarea merge mai departe de-a lungul uneia dintre ramurile arborelui. Dacă mediana nodului este complet în intervalul dat, atunci ambii subarbori trebuie vizitați.

Algoritm Z - nodul arborelui [( x_0_min , x_1_min , x_2_min ,..., x_n_min ),( x_0_max , x_1_max , x_2_max ,..., x_n_max )] - interval specificat Matrice de funcții ( Nodul *& Z ){ Dacă ([ x_0_min , x_1_min , x_2_min ,..., x_n_min ] < Z ){ Z = Z -> stânga ; // subarborele stânga } altfel Dacă ([ x_0_max , x_1_max , x_2_max ,..., x_n_max ] > Z ){ Z = Z -> dreapta ; // subarborele din dreapta } Altfel { // vizualizați ambii subarbori din Array ( Z -> dreapta ); // rulează funcția pentru subarborele din dreapta Z = Z -> stânga ; // vezi subarborele din stânga } } Analiză

Evident, numărul minim de elemente vizualizate este , unde este înălțimea arborelui. De asemenea, este evident că numărul maxim de elemente vizualizate este , adică vizualizarea tuturor elementelor arborelui. Rămâne de calculat numărul mediu de articole vizualizate . $Oh)$ $h$ $O(2^{h}-1)$ $Un}$

$[(x_{0_{min}},x_{1_{min}},x_{2_{min}},...,x_{n_{min}}),(x_{0_{max}} ,x_{1_{max}},x_{2_{max}},...,x_{n_{max}})]$ - interval dat.

Articolul original despre kd-trees oferă următoarea caracteristică: pentru un interval fix. $A_{n}=~O(h\cdot log(h))$

Dacă mergem de la înălțimea arborelui la numărul de elemente, atunci acesta va fi: $A_{n}=~O(log(log(n-1))^{log(n-1)})$

Găsirea celui mai apropiat vecin

Căutarea celui mai apropiat element este împărțită în două subsarcini: determinarea celui mai apropiat element posibil și găsirea celor mai apropiate elemente dintr-un interval dat.

Dat un copac . Coborâm copacul la frunzele sale în funcție de condiție și determinăm cel mai apropiat element probabil după condiție . După aceea, de la rădăcina arborelui, se lansează algoritmul pentru găsirea celui mai apropiat element din intervalul dat, care este determinat de raza . $arbore$ $arbore\la x[i](<,>=)arborele\la t$ $l_{min}={\sqrt {(({x_{0}-x[i]_{0)))^{2}+({x_{1}-x[i]_{1} })^{2}+...+({x_{n}-x[i]_{n}})^{2})}}$ $R=l_{min}={\sqrt {(({x_{0}-x[i]_{0)))^{2}+({x_{1}-x[i]_{ 1}})^{2}+...+({x_{n}-x[i]_{n}})^{2})}}$

Raza de căutare este ajustată atunci când este găsit un element mai apropiat.

Algoritm Z este rădăcina copacului Listă - o listă pentru cele mai apropiate elemente găsite [ x_0 , x_1 , x_2 ..., x_n ] - coordonatele tuturor dimensiunilor elementului nostru , pentru care cel mai apropiat Len - lungime minimă COPII - numărul maxim de copii pentru fiecare element Funcția Maybe_Near ( Node *& Z ) { // caută cel mai apropiat element posibil în timp ce ( Z ) { pentru ( i = 0 ; i < N ; i ++ ) { // verifica elementele din nodul len_cur = sqrt (( x_0 - x [ i ] _0 ) ^ 2 + ( x_1 - x [ i ] _1 ) ^ 2 + . .. + ( x_n - x [ i ] _n ) ^ 2 ); // lungimea elementului curent if ( Len > lungimea elementului curent ) { Len = len_cur ; // setează o nouă lungime Delete ( List ); // ștergerea listei Add ( List ); // adaugă un nou element la listă } else if ( lungimile sunt egale ) { Adăugați ( Lista ); // adaugă un nou element la listă } dacă (( x_0 == x [ i ] _0 ) && ( x_1 == x [ i ] _1 ) && ... && ( x_n == x [ i ] _n )) { întoarcere 1 ; } } dacă ([ x_0 , x_1 , x_2 ..., x_n ] < Z ) Z = Z -> stânga ; // subarborele stânga dacă ([ x_0 , x_1 , x_2 ..., x_n ] > Z ) Z = Z -> dreapta ; // subarborele din dreapta } } Funcția Aproape ( Nod *& Z ) { // caută recursiv cel mai apropiat element din intervalul dat dacă ( ! Z ) { returneaza Lista ; } len_cur = sqrt (( x_0 - x [ i ] _0 ) ^ 2 + ( x_1 - x [ i ] _1 ) ^ 2 + ... + ( x_n - x [ i ] _n ) ^ 2 ); // distanta de la punctul nostru la cel curent if ( len_cur < Len ) { // a gasit o lungime mai mica decat minima Len = len_cur ; // setează o nouă lungime minimă Delete ( List ); // ștergerea listei - la urma urmei, toate elementele găsite până acum sunt mai departe decât cea actuală Adaugă ( Listă , Z ); // adaugă elementul curent la listă } else if ( len_cur == Len ) { // lungimea este egală cu Adăugarea minimă ( List , Z ); // adaugă doar un element nou în listă } pentru ( i = 0 ; i < COPII ; i ++ ) { // faceți la fel pentru toți copiii Aproape ( Z -> copii [ i ]); // vezi toate subarborele } } Analiză

Evident, numărul minim de elemente vizualizate este , unde h este înălțimea arborelui. De asemenea, este evident că numărul maxim de elemente vizualizate este , adică vizualizarea tuturor nodurilor. Rămâne de calculat numărul mediu de articole vizualizate. $Oh)$ $O(2^{h}-1)$

$[(x_{0},x_{1},x_{2},...,x_{n})]$ este un element dat față de care doriți să găsiți cel mai apropiat. Această sarcină este împărțită în două subsarcini: găsirea celui mai apropiat element dintr-un nod și găsirea celui mai apropiat element dintr-un interval dat. Pentru a rezolva prima subproblemă, este necesară o coborâre de-a lungul copacului, adică . $Oh)$

Pentru a doua subsarcină, așa cum am calculat deja, căutarea elementelor dintr-un interval dat durează . Pentru a găsi media, adăugați pur și simplu aceste două valori: $O(h\cdot log(h))$

$=~O(h)+~O(h\cdot log(h))=~O(h)\cdot ({~O(log(h))+1}))$ .

Vezi și

Note

Link -uri

libkdtree++ , o implementare de tip STL open-source a arborilor k -d în C++.
Un tutorial despre KD Trees
FLANN și fork-ul său nanoplann , implementări eficiente C++ ale algoritmilor de arbore k -d.
kdtree O bibliotecă C simplă pentru lucrul cu KD-Trees
KD Tree Demo, applet Java Arhivat 29 iunie 2020 la Wayback Machine
Biblioteca libANN Approximate Nearest Neighbor include o implementare arbore k -d
Caseta de instrumente de căutare a imaginilor la scară largă Caltech : o cutie de instrumente Matlab care implementează un arbore k - d randomizat pentru căutarea rapidă aproximativă a celui mai apropiat vecin, în plus față de algoritmii de căutare LSH , K-Means ierarhici și Fișier inversat .
Algoritmi de tragere cu raze euristice , pp. 11 și după
Into conține implementări open source ale metodelor de căutare exacte și aproximative (k)NN folosind arbori k -d în C++.

Arborele (structura de date)
Arborele de căutare binar Arborele (teoria graficelor) structura arborelui
Arbori binari	arbore binar T-tree
Arbori binari cu auto-echilibrare	arbore AA arborele AVL Copac roșu-negru Splay arbore copac cu amenzi arbore cartezian Arborele Fibonacci B-arborele T-tree
B-copaci	2-3-copac B⁺-arborele B*-copac B x -arbore arborele UB 2-3-4 arbore (a,b)-copac copac dansant
arbori de prefix	arbore de sufix Arborele de prefix comprimat Arborele de căutare ternar
Partiționarea binară a spațiului	arbore k-dimensional arborele VP
Arbori non-binari	Quadtree octree Voxel rar Octree arbore exponenţial Arborele PQ
Despărțirea spațiului	R-arborele Arborele R Hilbert R+-arborele R*-copac X-arborele M-arbore Arborele Fenwick Arborele segmentului
Alți copaci	morman arbore de hash arborele degetelor arbore metric Arborele de acoperire BK-arborele Copac cu lanțuri duble iDistanța Arbore tăiat de legături Arborele LSM
Algoritmi	Lățimea prima căutare Profunzime prima căutare Algoritmul DSW protocolul spanning tree

Structuri de date
Liste	matrice listă legată individual listă dublu legată Lista de trecere
Copaci	B-arborele Arborele de căutare binar arborele AVL Copac roșu-negru morman
Contează	Graficul dirijat Graficul aciclic direcționat Diagrama de decizie binară Hipergraf
Alte	Tabel de hash Grămadă