Kd-træ

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 23. juli 2021; checks kræver 2 redigeringer .

K-dimensionelt træ

Type

Multidimensionelt træ Binært søgetræ

Opfindelsens år

1975

Forfatter

Jon Bentley

Kompleksitet i O-symboler

	Gennemsnit	I værste fald
Hukommelsesforbrug	O( n )	O( n )
Søg	O( logn )	O( n )
Indsæt	O( logn )	O( n )
Fjernelse	O( logn )	O( n )

Et k -d-træ ( eng. kd-træ , forkortelse for k-dimensionelt træ ) er enrumopdelt datastruktur til bestilling af punkter i et k - dimensionelt rum . k -d-træer bruges til nogle applikationer, såsom flerdimensionel nøglerumssøgning (rækkeviddesøgning og nærmeste nabosøgning ). k -d-træer er en særlig slags binære søgetræer .

Matematisk beskrivelse

Et K-dimensionelt træ er et ubalanceret søgetræ til lagring af punkter fra . Det giver en R-træ- lignende evne til at søge inden for et givet nøgleområde. Til skade for forespørgslens enkelhed er hukommelseskrav i stedet for . ${\mathbb {R}}^{k}$ $O(kn)$ $O((log(n))^{k-1})$

Der er homogene og ikke-homogene kd-træer. I homogene kd-træer gemmer hver node en post . I den heterogene variant indeholder interne noder kun nøgler, blade indeholder links til poster.

I et ikke-homogent kd-træ med et dimensionelt hyperplan parallelt med aksen i punktet . For roden skal du opdele punkterne gennem hyperplanet i to sæt punkter, der er så store som muligt og skrive til roden, til venstre for denne, alle punkter, som er gemt til, til højre, dem, for hvilke . For det venstre undertræ skal man opdele punkterne igen i et nyt "splitplan" og lagres i den interne node. Til venstre for dette, alle punkter, som . Dette fortsætter rekursivt over alle rum. Så starter alt igen fra det første rum, indtil hvert punkt tydeligt kan identificeres gennem hyperplanet. $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$

kd træ kan indbygges . En rækkeviddesøgning kan udføres i , hvorved størrelsen af svaret angives. Hukommelseskravet til selve træet er begrænset . $O(n(k+log(n)))$ $O(n^{1-{\frac {1}{k))}+a)$ $-en$ $O(kn)$

Operationer på k -d-træer

Struktur

Træstruktur beskrevet i C++ :

constexprint N = 10 ; _ // antal tasterum struct Item { // item structure int key [ N ]; // række af nøgler, der definerer elementet char * info ; // element information }; struct Node { // tree node structure Item i ; // element Node * venstre ; // venstre undertræ Node * højre ; // højre undertræ }

Træets struktur kan variere afhængigt af detaljerne i implementeringen af algoritmen . For eksempel kan en node indeholde et array i stedet for et enkelt element, hvilket forbedrer søgeeffektiviteten.

Elementsøgningsanalyse

Det mindste antal elementer, der ses, er naturligvis , og det maksimale antal elementer, der vises, er , hvor er højden på træet. Det er tilbage at beregne det gennemsnitlige antal sete varer . $en$ $O(h)$ $h$ $A_{n}$

$[x_{0},x_{1},x_{2},...,x_{n}]$ er det givne element.

Lad os overveje sagen . Fundne elementer kan være: $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.

og så videre for hvert tasterum. I dette tilfælde er den gennemsnitlige søgelængde i ét rum:

A={\frac {1+2+2+3+3+3+3}{7}}={\frac {17}{7}}\ca. 2.4

Gennemsnitsværdien beregnes med formlen: ${\displaystyle A_{n}=\sum _{k=1}^{n}kp_{n,k))$

Det er tilbage at finde sandsynligheden . Det er lig med , hvor er antallet af sager, hvornår og er det samlede antal sager. Det er ikke svært at gætte hvad . ${\displaystyle p_{n,k))$ ${\displaystyle p_{n,k}={\frac {p_{A,k}}{p_{n))))$ ${\displaystyle p_{A,k))$ $A=k$ $p_{n}$ $p_{n,k}={\frac {2^{k-1}}{2^{n}-1}}$

Vi erstatter dette med formlen for gennemsnitsværdien:

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}}\right)=

={\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))

altså hvor er træets højde. $A_{h}={\frac {2^{h}(h-1)+1}{2^{h}-1))$ $h$

Hvis vi går fra højden af træet til antallet af elementer, så:

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\left({\frac {n}{N}}+1\right))){2^{log\left({\frac {n}{N}}+1\right )}-1}}-1\right)=~O\left(log\left({\frac {n}{N}}+1\right){\frac {n+N}{n}}-1 \right)=

$=~O\left(log\left({\frac {n}{N}}+1\right)^{\frac {n+N}{n}}-1\right)$ , hvor er antallet af elementer i noden. $N$

Ud fra dette kan vi konkludere, at jo flere elementer der vil være indeholdt i noden, jo hurtigere vil træsøgningen være, da højden af træet forbliver minimal, men du bør ikke gemme et stort antal elementer i noden, da med denne metode kan hele træet degenerere til en normal matrix eller liste.

Tilføjelse af elementer

Tilføjelse af elementer foregår på nøjagtig samme måde som i et normalt binært søgetræ , med den eneste forskel, at hvert niveau i træet også vil blive bestemt af det rum, det tilhører.

Træprogressionsalgoritme:

for ( int i = 0 ; træ ; i ++ ) // i er mellemrumstallet if ( træ -> x [ i ] < træ -> t ) // t er mediantræet = træ - > venstre ; // flyt til venstre undertræ else træ = træ -> højre ; // flyt til højre undertræ

Tilføjelsen udføres efter , hvor er træets højde. $O(h)$ $h$

Fjernelse af elementer

Når du sletter træelementer, kan der opstå flere situationer:

Sletning af et træblad er en ret simpel sletning, når en node slettes, og forfaderknudemarkøren simpelthen nulstilles.

Fjernelse af en træknude (ikke et blad) er en meget kompliceret procedure, hvor du skal genopbygge hele undertræet for denne knude.

Nogle gange løses processen med at slette en node ved at ændre kd-træet. For eksempel, hvis vores node indeholder et array af elementer, så forbliver træknuden, når hele arrayet slettes, men nye elementer er ikke længere skrevet der.

Find en række elementer

Søgningen er baseret på normal trænedstigning, hvor hver knude kontrolleres for en rækkevidde. Hvis medianerne af en knude er mindre end eller større end et givet område i et givet rum, så går gennemgangen længere langs en af træets grene. Hvis medianen af noden er helt inden for det givne interval, skal begge undertræer besøges.

Algoritme Z - træknude _ [( x_0_min , x_1_min , x_2_min ,..., x_n_min ),( x_0_max , x_1_max , x_2_max ,..., x_n_max )] - specificeret interval Function Array ( Node *& Z ){ Hvis ([ x_0_min , x_1_min , x_2_min ,..., x_n_min ] < Z ){ Z = Z -> venstre ; // venstre undertræ } andet Hvis ([ x_0_max , x_1_max , x_2_max ,..., x_n_max ] > Z ){ Z = Z -> højre ; // højre undertræ } Ellers { // se begge undertræer af Array ( Z -> højre ); // kør funktionen for højre undertræ Z = Z -> venstre ; // se venstre undertræ } } Analyse

Det mindste antal elementer, der ses, er naturligvis , hvor er højden på træet. Det er også indlysende, at det maksimale antal elementer, der ses, er , dvs. at se alle elementer i træet. Det er tilbage at beregne det gennemsnitlige antal sete varer . $O(h)$ $h$ $O(2^{h}-1)$ $A_{n}$

$[(x_{0_{min}},x_{1_{min}},x_{2_{min}},...,x_{n_{min}}),(x_{0_{max}} ,x_{1_{max}},x_{2_{max}},...,x_{n_{max}})]$ - given rækkevidde.

Den originale artikel om kd-træer giver følgende karakteristika: for en fast rækkevidde. $A_{n}=~O(h\cdot log(h))$

Hvis vi går fra højden af træet til antallet af elementer, så vil dette være: $A_{n}=~O(log(log(n-1))^{log(n-1)})$

Find den nærmeste nabo

Søgningen efter det nærmeste element er opdelt i to delopgaver: at bestemme det mulige nærmeste element og finde de nærmeste elementer i et givet område.

Givet et træ . Vi sænker træet til dets blade efter tilstand og bestemmer det sandsynligt nærmeste element efter tilstand . Derefter lanceres fra roden af træet algoritmen til at finde det nærmeste element i det givne område, som er bestemt af radius . $træ$ $tree\to x[i](<,>=)tree\to 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})}}$

Søgeradius justeres, når et tættere element er fundet.

Algoritme Z er roden af træet Liste - en liste over de nærmeste fundne elementer [ x_0 , x_1 , x_2 ..., x_n ] - koordinater for alle dimensioner af vores element , for hvilke den nærmeste Len - minimum længde BØRN - det maksimale antal børn for hvert element Funktionen Maybe_Near ( Node *& Z ) { // søg efter det nærmeste mulige element, mens ( Z ) { for ( i = 0 ; i < N ; i ++ ) { // tjek elementer i node len_cur = sqrt (( x_0 - x [ i ] _0 ) ^ 2 + ( x_1 - x [ i ] _1 ) ^ 2 + . .. + ( x_n - x [ i ] _n ) ^ 2 ); // længde af nuværende element if ( Len > længde af nuværende element ) { Len = len_cur ; // sæt ny længde Slet ( Liste ); // rydde listen Tilføj ( Liste ); // tilføje et nyt element til listen } else if ( længder er ens ) { Tilføj ( Liste ); // tilføje et nyt element til listen } if (( x_0 == x [ i ] _0 ) && ( x_1 == x [ i ] _1 ) && ... && ( x_n == x [ i ] _n )) { retur 1 ; } } hvis ([ x_0 , x_1 , x_2 ..., x_n ] < Z ) Z = Z -> venstre ; // venstre undertræ hvis ([ x_0 , x_1 , x_2 ..., x_n ] > Z ) Z = Z -> højre ; // højre undertræ } } Funktion Nær ( Knudepunkt *& Z ) { // søg rekursivt efter det nærmeste element i det givne område, hvis ( ! Z ) { returnere Liste ; } len_cur = sqrt (( x_0 - x [ i ] _0 ) ^ 2 + ( x_1 - x [ i ] _1 ) ^ 2 + ... + ( x_n - x [ i ] _n ) ^ 2 ); // afstand fra vores punkt til det nuværende hvis ( len_cur < Len ) { // fandt en længde mindre end minimum Len = len_cur ; // indstilling af en ny minimumlængde Slet ( Liste ); // rydde listen - trods alt er alle elementer fundet indtil videre længere end det nuværende Tilføj ( List , Z ); // tilføje det aktuelle element til listen } else if ( len_cur == Len ) { // længden er lig med minimum Add ( List , Z ); // bare tilføje et nyt element til listen } for ( i = 0 ; i < BØRN ; i ++ ) { // gør det samme for alle børn Nær ( Z -> børn [ i ]); // se alle undertræer } } Analyse

Det mindste antal elementer, der ses, er naturligvis , hvor h er højden af træet. Det er også indlysende, at det maksimale antal elementer, der ses, er , dvs. at se alle noder. Det er tilbage at beregne det gennemsnitlige antal sete varer. $O(h)$ $O(2^{h}-1)$

$[(x_{0},x_{1},x_{2},...,x_{n})]$ er et givet element i forhold til hvilket du vil finde det nærmeste. Denne opgave er opdelt i to underopgaver: at finde det nærmeste element i en node og at finde det nærmeste element i et givet område. For at løse det første delproblem kræves der én nedstigning langs træet, det vil sige . $O(h)$

For den anden delopgave, som vi allerede har beregnet, tager søgningen efter elementer i et givet område . For at finde gennemsnittet skal du blot tilføje disse to værdier: $O(h\cdot log(h))$

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

Se også

Noter

Links

libkdtree++ , en open source STL-lignende implementering af k -d træer i C++.
En tutorial om KD-træer
FLANN og dets gaffel nanoflann , effektive C++ implementeringer af k -d træalgoritmer.
kdtree Et simpelt C-bibliotek til at arbejde med KD-træer
KD Tree Demo, Java-applet Arkiveret 29. juni 2020 på Wayback Machine
libANN Approximate Nearest Neighbor Library inkluderer en k -d- træimplementering
Caltech Large Scale Image Search Toolbox : en Matlab-værktøjskasse, der implementerer randomiseret k -d-træ til hurtig, tilnærmet nærmeste nabosøgning, foruden LSH , Hierarchical K-Means og Inverted File -søgealgoritmer.
Heuristiske stråleskydealgoritmer , s. 11 og efter
Into indeholder open source-implementeringer af eksakte og omtrentlige (k)NN-søgemetoder ved hjælp af k -d-træer i C++.

Træ (datastruktur)
Binært søgetræ Træ (grafteori) træstruktur
Binære træer	binært træ T-træ
Selvbalancerende binære træer	AA træ AVL træ Rød-sort træ Splay træ træ med bøder kartesisk træ Fibonacci træ B-træ T-træ
B-træer	2-3-træ B⁺-træ B*-træ B x -træ UB træ 2-3-4 træ (a,b)-træ dansende træ
præfiks træer	suffiks træ Komprimeret præfikstræ Ternært søgetræ
Binær opdeling af rummet	k-dimensionelt træ VP træ
Ikke-binære træer	Quadtree oktre Sparsom Voxel Octree eksponentielt træ PQ træ
At bryde rummet op	R-træ Hilbert R-træ R+-træ R*-træ X-træ M-træ Fenwick træ Segmenttræ
Andre træer	dynge hash træ fingertræ metrisk træ Belægning træ BK-træ Dobbeltkædet træ iDistance Linkskåret træ LSM træ
Algoritmer	Bredde først søgning Dybde første søgning DSW algoritme spanning tree protokol

Datastrukturer
Lister	array enkelt linket liste dobbelt linket liste Beståelsesliste
Træer	B-træ Binært søgetræ AVL træ Rød-sort træ dynge
Tæller	Instrueret graf rettet acyklisk graf Binært beslutningsdiagram Hypergraf
Andet	Hash bord Stak