Kd-träd

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 23 juli 2021; kontroller kräver 2 redigeringar .

K-dimensionellt träd

Sorts

Flerdimensionellt träd Binärt sökträd

Uppfinningens år

1975

Författare

Jon Bentley

Komplexitet i O-symboler

	Medel	Som värst
Minnesförbrukning	O( n )	O( n )
Sök	O( logga in )	O( n )
Föra in	O( logga in )	O( n )
Borttagning	O( logga in )	O( n )

Ett k -d-träd ( eng. kd-träd , förkortning för k-dimensionellt träd ) är enrymduppdelad datastruktur för att ordna punkter i ett k - dimensionellt utrymme . k -d-träd används för vissa applikationer såsom flerdimensionell nyckelrymdssökning (avståndssökning och närmaste grannesökning ). k -d-träd är en speciell typ av binära sökträd .

Matematisk beskrivning

Ett K-dimensionellt träd är ett obalanserat sökträd för att lagra punkter från . Den erbjuder en R-trädliknande förmåga att söka inom ett givet intervall av nycklar. Till nackdel för frågans enkelhet, minneskrav istället för . ${\mathbb {R}}^{k}$ $O(kn)$ $O((log(n))^{k-1})$

Det finns homogena och icke-homogena kd-träd. I homogena kd-träd lagrar varje nod en post . I den heterogena varianten innehåller interna noder endast nycklar, blad innehåller länkar till poster.

I ett icke-homogent kd-träd med ett dimensionellt hyperplan parallellt med axeln vid punkten . För roten måste du dela upp punkterna genom hyperplanet i två uppsättningar punkter som är så stora som möjligt och skriva till roten, till vänster om detta, alla punkter för vilka är lagrade , till höger, de för vilka . För det vänstra underträdet behöver man dela upp punkterna igen i ett nytt "delat plan" och lagras i den interna noden. Till vänster om detta, alla punkter för vilka . Detta fortsätter rekursivt över alla utrymmen. Sedan börjar allt igen från första utrymmet tills varje punkt tydligt kan identifieras genom 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äd kan byggas in . En intervallsökning kan utföras i , varvid anger storleken på svaret. Minneskravet för själva trädet är begränsat . $O(n(k+log(n)))$ $O(n^{1-{\frac {1}{k))}+a)$ $a$ $O(kn)$

Operationer på k -d-träd

Struktur

Trädstruktur som beskrivs i C++ :

constexprint N = 10 ; _ // antal tangentsteg struct Item { // item structure int key [ N ]; // array av nycklar som definierar elementet char * info ; // elementinformation }; struct Node { // trädnodsstruktur Item i ; // element Nod * vänster ; // vänster underträd Nod * höger ; // höger underträd }

Trädets struktur kan variera beroende på detaljerna i implementeringen av algoritmen . Till exempel kan en nod innehålla en array snarare än ett enda element, vilket förbättrar sökeffektiviteten.

Elementsökningsanalys

Uppenbarligen är det minsta antalet visade element , och det maximala antalet visade element är , där är trädets höjd. Det återstår att beräkna det genomsnittliga antalet visade objekt . $ett$ $Åh)$ $h$ $En}$

$[x_{0},x_{1},x_{2},...,x_{n}]$ är det givna elementet.

Låt oss överväga fallet . Hittade element kan vara: $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.

och så vidare för varje knappsats. I det här fallet är den genomsnittliga söklängden på ett utrymme:

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

Medelvärdet beräknas med formeln: ${\displaystyle A_{n}=\sum _{k=1}^{n}kp_{n,k))$

Det återstår att hitta sannolikheten . Det är lika med , där är antalet ärenden, när och är det totala antalet ärenden. Det är inte svårt att gissa vad . ${\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 ersätter detta med formeln för medelvärdet:

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

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

={\frac {1}{2^{n}-1}}\left(\summa _{k=1}^{n}{k2^{k}}+\summa _{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))

det vill säga var är höjden på trädet. $A_{h}={\frac {2^{h}(h-1)+1}{2^{h}-1))$ $h$

Om vi går från trädets höjd till antalet element, då:

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\höger))){2^{log\left({\frac {n}{N}}+1\höger )}-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)$ , där är antalet element i noden. $N$

Av detta kan vi dra slutsatsen att ju fler element som kommer att finnas i noden, desto snabbare blir trädsökningen, eftersom trädets höjd förblir minimal, men du bör inte lagra ett stort antal element i noden, eftersom med denna metod kan hela trädet urarta till en normal array eller lista.

Lägga till element

Att lägga till element sker på exakt samma sätt som i ett vanligt binärt sökträd , med den enda skillnaden att varje nivå i trädet också bestäms av det utrymme som det tillhör.

Trädprogressionsalgoritm:

för ( int i = 0 ; träd ; i ++ ) // i är mellanslagsnumret if ( träd -> x [ i ] < träd -> t ) // t är medianträdet = träd - > vänster ; // flytta till vänster underträd else träd = träd -> höger ; // flytta till höger underträd

Tillägget utförs efter , där är trädets höjd. $Åh)$ $h$

Ta bort element

När du tar bort trädelement kan flera situationer uppstå:

Att ta bort ett trädblad är en ganska enkel radering, när en nod raderas och förfädernodpekaren helt enkelt återställs till noll.

Att ta bort en trädnod (inte ett löv) är en mycket komplicerad procedur, där du måste bygga om hela underträdet för denna nod.

Ibland löses processen att ta bort en nod genom att modifiera kd-trädet. Till exempel, om vår nod innehåller en array av element, när hela arrayen raderas, finns trädnoden kvar, men nya element skrivs inte längre där.

Hitta en rad element

Sökningen baseras på normal trädnedstigning, där varje nod kontrolleras för ett intervall. Om medianerna för en nod är mindre än eller större än ett givet område i ett givet utrymme, så går övergången längre längs en av trädets grenar. Om medianen för noden är helt inom det givna intervallet måste båda underträden besökas.

Algoritm Z - trädnod _ [( x_0_min , x_1_min , x_2_min ,..., x_n_min ),( x_0_max , x_1_max , x_2_max ,..., x_n_max )] - specificerat intervall Function Array ( Node *& Z ){ Om ([ x_0_min , x_1_min , x_2_min ,..., x_n_min ] < Z ){ Z = Z -> vänster ; // vänster underträd } annan Om ([ x_0_max , x_1_max , x_2_max ,..., x_n_max ] > Z ){ Z = Z -> höger ; // höger underträd } Annars { // se båda underträden i Array ( Z -> höger ); // kör funktionen för det högra underträdet Z = Z -> vänster ; // visa vänster underträd } } Analys

Det minsta antalet element som visas är uppenbarligen , där är trädets höjd. Det är också uppenbart att det maximala antalet element som visas är , det vill säga att visa alla element i trädet. Det återstår att beräkna det genomsnittliga antalet visade objekt . $Åh)$ $h$ $O(2^{h}-1)$ $En}$

$[(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äckvidd.

Den ursprungliga artikeln om kd-träd ger följande egenskap: för ett fast intervall. $A_{n}=~O(h\cdot log(h))$

Om vi går från höjden på trädet till antalet element, kommer detta att vara: $A_{n}=~O(log(log(n-1))^{log(n-1)})$

Hitta närmaste granne

Sökandet efter det närmaste elementet är uppdelat i två deluppgifter: att bestämma det möjliga närmaste elementet och att hitta de närmaste elementen i ett givet intervall.

Givet ett träd . Vi sänker trädet till dess löv efter tillstånd och bestämmer det troligen närmaste elementet efter tillstånd . Efter det, från roten av trädet, lanseras algoritmen för att hitta det närmaste elementet i det givna området, som bestäms av radien . ${\displaystyle-träd}$ $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ökradien justeras när ett närmare element hittas.

Algoritm Z är trädets rot Lista - en lista över de närmast hittade elementen [ x_0 , x_1 , x_2 ..., x_n ] - koordinater för alla dimensioner av vårt element , för vilka den närmaste Len - minsta längd BARN - det maximala antalet barn för varje element Funktionen Maybe_Near ( Node *& Z ) { // sök efter det närmaste möjliga elementet medan ( Z ) { for ( i = 0 ; i < N ; i ++ ) { // kontrollera element i noden len_cur = sqrt (( x_0 - x [ i ] _0 ) ^ 2 + ( x_1 - x [ i ] _1 ) ^ 2 + . .. + ( x_n - x [ i ] _n ) ^ 2 ); // längd på nuvarande element if ( Len > längd på nuvarande element ) { Len = len_cur ; // ställ in ny längd Ta bort ( Lista ); // rensa listan Lägg till ( Lista ); // lägg till ett nytt element i listan } else if ( längder är lika ) { Lägg till ( Lista ); // lägg till ett nytt element i listan } if (( x_0 == x [ i ] _0 ) && ( x_1 == x [ i ] _1 ) && ... && ( x_n == x [ i ] _n )) { retur 1 ; } } om ([ x_0 , x_1 , x_2 ..., x_n ] < Z ) Z = Z -> vänster ; // vänster underträd om ([ x_0 , x_1 , x_2 ..., x_n ] > Z ) Z = Z -> höger ; // höger underträd } } Funktion Nära ( Node *& Z ) { // söker rekursivt efter det närmaste elementet i det givna intervallet om ( ! Z ) { returnera Lista ; } len_cur = sqrt (( x_0 - x [ i ] _0 ) ^ 2 + ( x_1 - x [ i ] _1 ) ^ 2 + ... + ( x_n - x [ i ] _n ) ^ 2 ); // avstånd från vår punkt till den nuvarande om ( len_cur < Len ) { // hittade en längd som är mindre än den minsta Len = len_cur ; // ställa in en ny minimilängd Delete ( List ); // rensa listan - trots allt är alla element som hittats hittills längre än det nuvarande Add ( List , Z ); // add the current element to the list } else if ( len_cur == Len ) { // längden är lika med minimum Add ( List , Z ); // lägg bara till ett nytt element i listan } for ( i = 0 ; i < BARN ; i ++ ) { // gör samma sak för alla barn Nära ( Z -> barn [ i ]); // visa alla underträd } } Analys

Det minsta antalet element som visas är uppenbarligen , där h är trädets höjd. Det är också uppenbart att det maximala antalet element som visas är , det vill säga att visa alla noder. Det återstår att beräkna det genomsnittliga antalet visade objekt. $Åh)$ $O(2^{h}-1)$

$[(x_{0},x_{1},x_{2},...,x_{n})]$ är ett givet element med avseende på vilket du vill hitta det närmaste. Denna uppgift är uppdelad i två deluppgifter: att hitta det närmaste elementet i en nod och att hitta det närmaste elementet i ett givet intervall. För att lösa det första delproblemet krävs en nedstigning längs trädet, det vill säga . $Åh)$

För den andra deluppgiften, som vi redan har beräknat, tar sökningen efter element i ett givet intervall . För att hitta genomsnittet, lägg till dessa två värden: $O(h\cdot log(h))$

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

Se även

Anteckningar

Länkar

libkdtree++ , en öppen källkod STL-liknande implementering av k -d träd i C++.
En handledning om KD Trees
FLANN och dess gaffel nanoflann , effektiva C++-implementationer av k -d-trädalgoritmer .
kdtree Ett enkelt C-bibliotek för att arbeta med KD-träd
KD Tree Demo, Java-applet Arkiverad 29 juni 2020 på Wayback Machine
libANN Approximate Nearest Neighbor Library inkluderar en k -d- trädimplementering
Caltech storskalig bildsökningsverktygslåda : en Matlab-verktygslåda som implementerar randomiserat k -d-träd för snabb ungefärlig sökning av närmaste grannar, förutom LSH , Hierarkiska K-medel och inverterade filsökningsalgoritmer .
Heuristic Ray Shooting Algorithms , s. 11 och efter
Into innehåller öppen källkodsimplementeringar av exakta och ungefärliga (k)NN-sökningsmetoder som använder k -d-träd i C++.

Träd (datastruktur)
Binärt sökträd Träd (grafteori) trädstruktur
Binära träd	binärt träd T-träd
Självbalanserande binära träd	AA-träd AVL-träd Röd-svart träd Splay träd träd med böter kartesiskt träd Fibonacci träd B-träd T-träd
B-träd	2-3-träd B⁺-träd B*-träd B x -träd UB-träd 2-3-4 träd (a,b)-träd dansande träd
prefix träd	suffixträd Komprimerat prefixträd Ternärt sökträd
Binär uppdelning av utrymme	k-dimensionellt träd VP-träd
Icke-binära träd	Quadtree octree Gles Voxel Octree exponentiellt träd PQ-träd
Bryter upp utrymmet	R-träd Hilbert R-träd R+-träd R*-träd X-träd M-träd Fenwick träd Segment träd
Andra träd	högen haschträd fingerträd metriskt träd Beläggning träd BK-träd Dubbelkedjat träd iDistance Länkklippt träd LSM-träd
Algoritmer	Utöka första sökningen Djup första sökning DSW-algoritm spaning tree-protokoll

Data struktur
Listor	array enbart länkad lista dubbelt länkad lista Passlista
Träd	B-träd Binärt sökträd AVL-träd Röd-svart träd högen
Räknar	Riktad graf Riktad acyklisk graf Binärt beslutsdiagram Hypergraf
Övrig	Hashbord Stack