Päällystyspuu

Kansipuu on puumainen tietorakenne ( puu ), joka on erityisesti suunniteltu nopeuttamaan lähimmän naapurin hakua .

Puuta voidaan pitää hierarkiana, jonka ylin taso sisältää juuripisteen ja alin taso sisältää kaikki metrisen tilan pisteet . Jokainen taso vastaa kokonaislukua , joka pienenee yhdellä kullakin alemmalla tasolla. Jokaisella kattavuuspuun tasolla on kolme tärkeää ominaisuutta: $C$ $i$ $C$

Pesiminen: ${\displaystyle C_{i}\subseteq C_{i-1))$
Kattavuus: Jokaiselle pisteelle on olemassa sellainen piste , että etäisyys kohteeseen on pienempi tai yhtä suuri kuin ja täsmälleen yksi tällainen piste on pisteen esi-isä . $p\in C_{i-1}$ ${\displaystyle q\in C_{i))$ $s$ $q$ ${\näyttötyyli 2^{i))$ $q$ $s$
Erotus: Kaikkien pisteiden etäisyys kohteeseen on suurempi tai yhtä suuri kuin . ${\displaystyle p,q\in C_{i))$ $s$ $q$ ${\näyttötyyli 2^{i))$

Laskennallinen monimutkaisuus

Hae

Lisää

Muisti

Katso myös

Linkit

Alina Beygelzimer, Sham Kakade ja John Langford. Peitä puita lähimmälle naapurille. Julkaisussa Proc. Kansainvälinen koneoppimiskonferenssi (ICML), 2006.
John Langfordin kansilehti .
Kansipuun toteutus C++:ssa .

Puu (tietorakenne)
Binäärihakupuu Puu (graafiteoria) puun rakenne
Binääripuut	binääripuu T-puu
Itsetasapainottavat binaaripuut	AA puu AVL puu Puna-musta puu Splay-puu puu sakkoilla karteesinen puu Fibonacci puu B-puu T-puu
B-puut	2-3-puu B⁺-puu B*-puu B x -puu UB puu 2-3-4 puu (a,b)-puu tanssiva puu
etuliite puita	suffiksi puu Pakattu etuliitepuu Kolmiosainen hakupuu
Avaruuden binaarinen osiointi	k-ulotteinen puu VP-puu
Ei-binääripuut	Quadtree oktreen Harva Voxel Octree eksponentiaalinen puu PQ puu
Avaruuden hajottaminen	R-puu Hilbert R-puu R+-puu R*-puu X-puu M-puu Fenwick puu Segmenttipuu
Muut puut	pino hash puu sormipuu metrinen puu Päällystyspuu BK-puu Kaksiketjuinen puu iDistance Linkistä leikattu puu LSM puu
Algoritmit	Leveys ensimmäinen haku Ensimmäinen syvyyshaku DSW-algoritmi kattava puu protokolla