Beläggning träd

Ett täckträd är en trädliknande datastruktur ( träd ) speciellt utformad för att påskynda sökningen av närmaste grannar .

Ett träd kan ses som en hierarki, där den översta nivån innehåller rotpunkten och den nedre nivån innehåller alla punkter i ett metriskt utrymme . Varje nivå motsvarar ett heltal , som minskar med ett på varje lägre nivå. Varje nivå i täckningsträdet har tre viktiga egenskaper: $C$ $i$ $C$

Häckande: ${\displaystyle C_{i}\subseteq C_{i-1))$
Täckning: För varje punkt finns det en punkt så att avståndet från till är mindre än eller lika med och exakt en sådan punkt är en förfader till punkten . $p\in C_{i-1}$ ${\displaystyle q\in C_{i))$ $sid$ $q$ ${\displaystyle 2^{i))$ $q$ $sid$
Separation: För alla punkter är avståndet från till större än eller lika med . ${\displaystyle p,q\in C_{i))$ $sid$ $q$ ${\displaystyle 2^{i))$

Beräkningskomplexitet

Sök

Infoga

Minne

Se även

Länkar

Alina Beygelzimer, Sham Kakade och John Langford. Täck träd för närmaste granne. I Proc. Internationell konferens om maskininlärning (ICML), 2006.
John Langfords omslagsträdsida .
Implementering av täckträ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