Belægning træ

Et dæktræ er en trælignende datastruktur ( træ ) , der er specielt designet til at fremskynde den nærmeste nabosøgning .

Et træ kan opfattes som et hierarki, hvor det øverste niveau indeholder rodpunktet og det nederste niveau indeholder alle punkter i et metrisk rum . Hvert niveau svarer til et heltal , som falder med et på hvert lavere niveau. Hvert niveau i dækningstræet har tre vigtige egenskaber: $C$ $jeg$ $C$

Indlejring: ${\displaystyle C_{i}\subseteq C_{i-1))$
Dækning: For hvert punkt er der et punkt , således at afstanden fra til er mindre end eller lig med, og præcis et sådant punkt er en forfader til punktet . $p\in C_{i-1}$ ${\displaystyle q\in C_{i))$ $s$ $q$ ${\displaystyle 2^{i))$ $q$ $s$
Adskillelse: For alle punkter er afstanden fra til større end eller lig med . ${\displaystyle p,q\in C_{i))$ $s$ $q$ ${\displaystyle 2^{i))$

Beregningsmæssig kompleksitet

Søg

Indsæt

Hukommelse

Se også

Links

Alina Beygelzimer, Sham Kakade og John Langford. Dæk træer til nærmeste nabo. I Proc. International konference om maskinlæring (ICML), 2006.
John Langfords forsidetræ-side .
Cover tree implementering 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