Potahový strom

Strom pokrytí je stromová datová struktura ( strom ) speciálně navržená pro urychlení vyhledávání nejbližšího souseda .

Strom si lze představit jako hierarchii, přičemž nejvyšší úroveň obsahuje kořenový bod a spodní úroveň obsahuje všechny body v metrickém prostoru . Každá úroveň odpovídá celému číslu , které se v každé nižší úrovni snižuje o jednu. Každá úroveň ve stromu pokrytí má tři důležité vlastnosti: $C$ $i$ $C$

Vnoření: ${\displaystyle C_{i}\subseteq C_{i-1))$
Pokrytí: Pro každý bod existuje bod , jehož vzdálenost od do je menší nebo rovna a přesně jeden takový bod je předkem bodu . $p\in C_{i-1}$ ${\displaystyle q\in C_{i))$ $p$ $q$ ${\displaystyle 2^{i))$ $q$ $p$
Separace: U všech bodů je vzdálenost od do větší nebo rovna . ${\displaystyle p,q\in C_{i))$ $p$ $q$ ${\displaystyle 2^{i))$

Výpočetní složitost

Hledat

Vložit

Paměť

Viz také

Odkazy

Alina Beygelzimer, Sham Kakade a John Langford. Krycí stromy pro nejbližšího souseda. V Proc. Mezinárodní konference o strojovém učení (ICML), 2006.
John Langford's Cover Tree page .
Implementace stromu titulků 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