Bevonat fa

A fedőfa egy faszerű adatstruktúra ( fa ) , amelyet kifejezetten a legközelebbi szomszéd keresésének felgyorsítására terveztek .

A fát hierarchiának tekinthetjük, ahol a legfelső szint a gyökérpontot, az alsó szint pedig egy metrikus tér összes pontját tartalmazza . Minden szint egy egész számnak felel meg , amely minden alsó szinten eggyel csökken. A lefedettségi fa minden szintjének három fontos tulajdonsága van: $C$ $én$ $C$

Fészkelődés: ${\displaystyle C_{i}\subseteq C_{i-1))$
Lefedettség: Minden ponthoz van egy olyan pont , amelynek távolsága ig kisebb vagy egyenlő, és pontosan egy ilyen pont a pont őse . $p\in C_{i-1}$ ${\displaystyle q\in C_{i))$ $p$ $q$ ${\displaystyle 2^{i))$ $q$ $p$
Elválasztás: Minden pont esetén a távolság -tól nagyobb vagy egyenlő, mint . ${\displaystyle p,q\in C_{i))$ $p$ $q$ ${\displaystyle 2^{i))$

Számítási összetettség

Keresés

Beszúrás

Memória

Lásd még

Linkek

Alina Beygelzimer, Sham Kakade és John Langford. Takarja le a fákat a legközelebbi szomszédnak. In Proc. Nemzetközi Gépi Tanulási Konferencia (ICML), 2006.
John Langford borítófa oldala .
Cover fa megvalósítása C++ nyelven .

Fa (adatstruktúra)
Bináris keresőfa Fa (gráfelmélet) fa szerkezet
Bináris fák	bináris fa T-fa
Önkiegyensúlyozó bináris fák	AA fa AVL fa Vörös-fekete fa Splay fa fa bírságokkal karteziánus fa Fibonacci fa B-fa T-fa
B-fák	2-3-fa B⁺-fa B*-fa B x -fa UB fa 2-3-4 fa (a,b)-fa táncoló fa
előtag fák	utótag fa Tömörített előtag fa hármas keresőfa
A tér bináris particionálása	k-dimenziós fa VP fa
Nem bináris fák	Quadtree oktfa Ritka Voxel Octree exponenciális fa PQ fa
A tér felosztása	R-fa Hilbert R-fa R+-fa R*-fa X-fa M-fa Fenwick fa Szegmens fa
Más fák	halom hash fa ujjfa metrikus fa Bevonat fa BK-fa Kétláncú fa iDistance Link-vágott fa LSM fa
Algoritmusok	Szélesség első keresés Mélységi első keresés DSW algoritmus átívelő fa protokoll