Kd-strom

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 23. července 2021; kontroly vyžadují 2 úpravy .

K-rozměrný strom

Typ

Vícerozměrný strom Binární vyhledávací strom

Rok vynálezu

1975

Autor

Jon Bentley

Složitost v O-symbolech

	Průměrný	Při nejhorším
Spotřeba paměti	O( n )	O( n )
Vyhledávání	O( logn )	O( n )
Vložit	O( logn )	O( n )
Odstranění	O( logn )	O( n )

K -d-tree ( angl. kd tree , zkratka pro k-dimenzionální strom ) jeprostorově rozdělená datová struktura pro uspořádání bodů v k - rozměrném prostoru . k -d-stromy se používají pro některé aplikace, jako je vyhledávání vícerozměrných klíčů (prohledávání rozsahu a vyhledávání nejbližšího souseda ). k -d-stromy jsou speciálním druhem binárních vyhledávacích stromů .

Matematický popis

K-rozměrný strom je nevyvážený vyhledávací strom pro ukládání bodů z . Nabízí schopnost typu R-tree vyhledávat v daném rozsahu klíčů. Na úkor jednoduchosti dotazu jsou požadavky na paměť místo . ${\mathbb {R}}^{k}$ $O(kn)$ $O((log(n))^{k-1})$

Existují homogenní a nehomogenní kd-stromy. V homogenních kd-stromech každý uzel ukládá záznam . V heterogenní variantě obsahují interní uzly pouze klíče, listy obsahují odkazy na záznamy.

V nehomogenním kd-stromu s -rozměrnou nadrovinou rovnoběžnou s osou v bodě . Pro kořen musíte rozdělit body přes nadrovinu na dvě sady bodů, které jsou co největší a zapsat do kořene, nalevo od něj, všechny body, pro které jsou uloženy , napravo ty, pro které . Pro levý podstrom je potřeba body opět rozdělit do nové "rozdělovací roviny" a je uložena ve vnitřním uzlu. Nalevo od toho jsou všechny body, za které . Toto pokračuje rekurzivně přes všechny prostory. Pak vše začíná znovu od prvního prostoru, dokud nelze každý bod jasně identifikovat přes nadrovinu. $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 strom lze zabudovat . Hledání rozsahu lze provést v , přičemž označuje velikost odpovědi. Paměťové nároky na samotný strom jsou omezené . $O(n(k+log(n)))$ $O(n^{1-{\frac {1}{k}}}+a)$ $A$ $O(kn)$

Operace na k -d-stromech

Struktura

Stromová struktura popsaná v C++ :

constexprint N = 10 ; _ // počet keyspace struct Položka { // struktura položky int klíč [ N ]; // pole klíčů definujících prvek char * info ; // informace o prvku }; struct Node { // stromová struktura uzlu Item i ; // element Node * left ; // levý podstrom Uzel * pravý ; // pravý podstrom }

Struktura stromu se může lišit v závislosti na detailech implementace algoritmu . Například uzel může obsahovat pole spíše než jeden prvek, což zlepšuje efektivitu vyhledávání.

Analýza vyhledávání prvků

Je zřejmé, že minimální počet zobrazených prvků je a maximální počet zobrazených prvků je , kde je výška stromu. Zbývá vypočítat průměrný počet zhlédnutých položek . $jeden$ $Ach)$ $h$ $A_{n}$

$[x_{0},x_{1},x_{2},...,x_{n}]$ je daný prvek.

Zvažme případ . Nalezené prvky mohou být: $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.

a tak dále pro každý klíčový prostor. V tomto případě je průměrná délka vyhledávání v jednom prostoru:

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

Průměrná hodnota se vypočítá podle vzorce: ${\displaystyle A_{n}=\sum _{k=1}^{n}kp_{n,k))$

Zbývá najít pravděpodobnost . Rovná se , kde je počet případů, kdy a je celkový počet případů. Není těžké uhodnout co . ${\displaystyle p_{n,k))$ ${\displaystyle 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}}$

Dosadíme to do vzorce pro průměrnou hodnotu:

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(\součet _{k+1=1}^{n}{k2^{k}}+\součet _{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))

to znamená , kde je výška stromu. $A_{h}={\frac {2^{h}(h-1)+1}{2^{h}-1))$ $h$

Pokud přejdeme od výšky stromu k počtu prvků, pak:

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)$ , kde je počet prvků v uzlu. $N$

Z toho můžeme usoudit, že čím více prvků bude v uzlu obsaženo, tím rychlejší bude vyhledávání stromu, protože výška stromu zůstane minimální, ale neměli byste do uzlu ukládat velké množství prvků, protože s touto metodou se může celý strom zvrhnout na normální pole nebo seznam.

Přidávání prvků

Přidávání prvků probíhá úplně stejným způsobem jako v běžném binárním vyhledávacím stromu , jen s tím rozdílem, že každá úroveň stromu bude také určena prostorem, do kterého patří.

Algoritmus progrese stromu:

for ( int i = 0 ; strom ; i ++ ) // i je číslo prostoru if ( strom -> x [ i ] < strom -> t ) // t je střední strom = strom -> vlevo ; // přesun do levého podstromu else strom = strom -> vpravo ; // přesun do pravého podstromu

Přidání se provádí za , kde je výška stromu. $Ach)$ $h$

Odebírání prvků

Při mazání prvků stromu může nastat několik situací:

Odstranění listu stromu je poměrně jednoduché odstranění, kdy je odstraněn jeden uzel a ukazatel uzlu předka je jednoduše resetován na nulu.

Odstranění uzlu stromu (nikoli listu) je velmi složitá procedura, ve které musíte přestavět celý podstrom pro tento uzel.

Někdy se proces smazání uzlu řeší úpravou kd-stromu. Pokud například náš uzel obsahuje pole prvků, pak při smazání celého pole uzel stromu zůstane, ale nové prvky se tam již nezapisují.

Nalezení řady prvků

Vyhledávání je založeno na normálním sestupu stromu, kde se každý uzel kontroluje na rozsah. Pokud jsou mediány uzlu menší nebo větší než daný rozsah v daném prostoru, pak procházení pokračuje dále podél jedné z větví stromu. Pokud je medián uzlu zcela v daném rozsahu, pak je nutné navštívit oba podstromy.

Algoritmus Z - uzel stromu [( x_0_min , x_1_min , x_2_min ,..., x_n_min ),( x_0_max , x_1_max , x_2_max ,..., x_n_max )] – zadaný rozsah Function Array ( Node *& Z ){ If ([ x_0_min , x_1_min , x_2_min ,..., x_n_min ] < Z ){ Z = Z -> vlevo ; // levý podstrom } jiný If ([ x_0_max , x_1_max , x_2_max ,..., x_n_max ] > Z ){ Z = Z -> vpravo ; // pravý podstrom } Else { // zobrazení obou podstromů Array ( Z -> vpravo ); // spustíme funkci pro pravý podstrom Z = Z -> left ; // zobrazit levý podstrom } } Analýza

Je zřejmé, že minimální počet zobrazených prvků je , kde je výška stromu. Je také zřejmé, že maximální počet zobrazených prvků je , tedy zobrazení všech prvků stromu. Zbývá vypočítat průměrný počet zhlédnutých položek . $Ach)$ $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}})]$ - daný rozsah.

Původní článek o kd-stromech uvádí následující charakteristiku: pro pevný rozsah. $A_{n}=~O(h\cdot log(h))$

Pokud přejdeme z výšky stromu na počet prvků, bude to: $A_{n}=~O(log(log(n-1))^{log(n-1)})$

Hledání nejbližšího souseda

Hledání nejbližšího prvku je rozděleno do dvou dílčích úkolů: určení možného nejbližšího prvku a nalezení nejbližších prvků v daném rozsahu.

Daný strom . Sestoupíme strom k jeho listům podle podmínky a určíme pravděpodobný nejbližší prvek podle podmínky . Poté se z kořene stromu spustí algoritmus pro nalezení nejbližšího prvku v daném rozsahu, který je určen poloměrem . $tree$ $tree\to x[i](<,>=)strom\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})}}$

Poloměr hledání se upraví, když je nalezen bližší prvek.

Algoritmus Z je kořen stromu Seznam – seznam nejbližších nalezených prvků _ [ x_0 , x_1 , x_2 ... , x_n ] - souřadnice všech rozměrů našeho prvku , pro které je nejbližší Len - minimální délka DĚTI - maximální počet dětí pro každý prvek Funkce Maybe_Near ( Node *& Z ) { // hledání nejbližšího možného prvku while ( Z ) { for ( i = 0 ; i < N ; i ++ ) { // kontrola prvků v uzlu len_cur = sqrt (( x_0 - x [ i ] _0 ) ^ 2 + ( x_1 - x [ i ] _1 ) ^ 2 + . .. + ( x_n - x [ i ] _n ) ^ 2 ); // délka aktuálního prvku if ( Délka > délka aktuálního prvku ) { Len = len_cur ; // nastavení nové délky Delete ( List ); // vymazání seznamu Add ( List ); // přidat nový prvek do seznamu } else if ( délky se rovnají ) { Přidat ( Seznam ); // přidat nový prvek do seznamu } if (( x_0 == x [ i ] _0 ) && ( x_1 == x [ i ] _1 ) && ... && ( x_n == x [ i ] _n )) { návrat 1 ; } } if ([ x_0 , x_1 , x_2 ..., x_n ] < Z ) Z = Z -> vlevo ; // levý podstrom if ([ x_0 , x_1 , x_2 ..., x_n ] > Z ) Z = Z -> vpravo ; // pravý podstrom } } Funkce Near ( Node *& Z ) { // rekurzivně vyhledá nejbližší prvek v daném rozsahu if ( ! Z ) { vrátit Seznam ; } len_cur = sqrt (( x_0 - x [ i ] _0 ) ^ 2 + ( x_1 - x [ i ] _1 ) ^ 2 + ... + ( x_n - x [ i ] _n ) ^ 2 ); // vzdálenost od našeho bodu k aktuálnímu if ( len_cur < Len ) { // nalezena délka menší než minimální Len = len_cur ; // nastavení nové minimální délky Delete ( List ); // vymazání seznamu - vždyť všechny dosud nalezené prvky jsou dále než ten aktuální Add ( List , Z ); // přidá aktuální prvek do seznamu } else if ( len_cur == Len ) { // délka je rovna minimu Add ( List , Z ); // stačí přidat nový prvek do seznamu } for ( i = 0 ; i < CHILDREN ; i ++ ) { // proveďte totéž pro všechny děti Blízko ( Z -> děti [ i ]); // zobrazit všechny podstromy } } Analýza

Je zřejmé, že minimální počet zobrazených prvků je , kde h je výška stromu. Je také zřejmé, že maximální počet prohlížených prvků je , tedy zobrazení všech uzlů. Zbývá vypočítat průměrný počet zhlédnutých položek. $Ach)$ $O(2^{h}-1)$

$[(x_{0},x_{1},x_{2},...,x_{n})]$ je daný prvek, ke kterému chcete najít ten nejbližší. Tento úkol je rozdělen do dvou dílčích úkolů: nalezení nejbližšího prvku v uzlu a nalezení nejbližšího prvku v daném rozsahu. K vyřešení prvního dílčího problému je zapotřebí jeden sestup podél stromu, tedy . $Ach)$

U druhého dílčího úkolu, jak jsme již spočítali, trvá hledání prvků v daném rozsahu . Chcete-li zjistit průměr, jednoduše přidejte tyto dvě hodnoty: $O(h\cdot log(h))$

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

Viz také

Poznámky

Odkazy

libkdtree++ , open-source STL implementace k -d stromů v C++.
Návod na KD Trees
FLANN a jeho vidlice nanoflann , efektivní C++ implementace k -d stromových algoritmů.
kdtree Jednoduchá C knihovna pro práci s KD-Stromy
KD Tree Demo, Java applet Archivováno 29. června 2020 na Wayback Machine
Knihovna libANN Approximate Nearest Neighbor Library obsahuje implementaci stromu k -d
Caltech Large Scale Image Search Toolbox : sada nástrojů Matlab implementující randomizovaný k - d strom pro rychlé přibližné vyhledávání nejbližších sousedů, navíc s LSH , Hierarchical K-Means a algoritmy pro vyhledávání invertovaných souborů .
Heuristické algoritmy Ray Shooting , str. 11 a později
Into obsahuje open source implementace přesných a přibližných (k)NN vyhledávacích metod pomocí k -d stromů v C++.

Strom (datová struktura)
Binární vyhledávací strom Strom (teorie grafů) stromová struktura
Binární stromy	binární strom T-strom
Samovyrovnávací binární stromy	AA strom strom AVL Červeno-černý strom Rozvětvený strom strom s pokutami karteziánský strom Fibonacciho strom B-strom T-strom
B-stromy	2-3-strom B⁺-strom B*-strom B x -strom UB strom 2-3-4 strom (a,b)-strom tančící strom
předponové stromy	příponový strom Komprimovaný strom předpon Ternární vyhledávací strom
Binární dělení prostoru	k-rozměrný strom VP strom
Nebinární stromy	Čtyřstrom oktree Řídký Voxel Octree exponenciální strom PQ strom
Rozbití prostoru	R-strom Hilbertův R-strom R+-strom R*-strom X-strom M-strom Fenwickův strom Segmentový strom
Jiné stromy	halda hash tree prstový strom metrický strom Potahový strom BK-strom Dvouřetězový strom iVzdálenost Link-cut strom LSM strom
Algoritmy	Šířka první hledání Hloubka první hledání Algoritmus DSW protokol spanning tree

Datové struktury
Seznamy	pole jednotlivě propojený seznam dvojitě propojený seznam Seznam průchodů
Stromy	B-strom Binární vyhledávací strom strom AVL Červeno-černý strom halda
Počítání	Orientovaný graf Orientovaný acyklický graf Binární rozhodovací diagram Hypergraf
jiný	Hash tabulka Zásobník