Fibonacci fa

A Fibonacci fa egy AVL fa , amelynek a legkisebb csúcsszáma van egy adott magassághoz (mélységhez).

Ha bármelyik csúcsra annak a részfának a magassága, amelynek ez a csúcsa a gyöke , akkor ennek a csúcsnak a jobb és bal oldali részfáinak magassága egyenlő és , vagy és . A Fibonacci fa minden részfája egyben Fibonacci fa is. $h$ $h-1$ $h-2$ $h-2$ $h-1$
Az üres fa egy 0 magasságú Fibonacci fa.
Az egy csúcsú fa egy 1-es magasságú Fibonacci-fa.

Csúcsok száma

A Fibonacci-fa egyik nagyon lényeges tulajdonsága, hogy a benne lévő csúcsok száma csak egy bizonyos értékkészletet vehet fel. Legyen a Fibonacci fa csúcsainak száma magassággal , akkor , és tetszőleges h esetén a csúcsok száma rekurzív módon leírható : . A Fibonacci-fát azért nevezték így el, mert a fenti képlet hasonló a Fibonacci-számok sorozatát meghatározó ismétlődési relációhoz . Magasság esetén a csúcsok száma , ahol a -edik Fibonacci-szám. ${\displaystyle N_{h))$ $h$ $N_{0}=0$ $N_{1}=1$ $N_{h}=N_{h-1}+N_{h-2}+1$ $h$ $N_{h}=\Phi _{h+2}-1$ ${\displaystyle \Phi _{n))$ $n$

Lásd még

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