Arborele Fibonacci

Arborele Fibonacci de înălțime 5

Arborele Fibonacci este un arbore AVL care, având o înălțime dată, are cel mai mic număr posibil de noduri, menținând în același timp echilibrul.

Acest tip special de copac își ia numele de la matematicianul omonim Leonardo Fibonacci . Arborele are de fapt caracteristicile faimoasei succesiuni, este de fapt intrinsec recursiv. Se poate observa din faptul că orice copac Fibonacci de înălțime h poate fi construit pornind de la o rădăcină și un subarbore de înălțime h-2 ca subarborele drept și h-1 ca subarborele stâng.

Se verifică intuitiv și vizual că coeficientul de echilibru al fiecărui nod unic al arborelui este +1 . Deci, această categorie de copaci este cea care se apropie cel mai mult de starea dezechilibrată, deși evident încă echilibrată.

Înălțime lemă

Afirmație

Este ${\mathcal {T}}_{h}$ ${\ displaystyle {\ mathcal {T}} _ {h}}$ ${\ displaystyle {\ mathcal {T}} _ {h}}$ un copac înalt Fibonacci $h$ ${\ displaystyle h}$ $h$ și fie ${\mathit {n}}_{h}$ ${\ displaystyle {\ mathit {n}} _ {h}}$ ${\ displaystyle {\ mathit {n}} _ {h}}$ numărul nodurilor sale. Se pare ${\mathit {h}}=\theta (\log n_{h})$ ${\ displaystyle {\ mathit {h}} = \ theta (\ log n_ {h})}$ ${\ displaystyle {\ mathit {h}} = \ theta (\ log n_ {h})}$

Demonstrație

Prin însăși natura arborelui Fibonacci, se dovedește că ${\mathit {n}}_{h}$ ${\ displaystyle {\ mathit {n}} _ {h}}$ ${\ displaystyle {\ mathit {n}} _ {h}}$ $=1+{\mathit {n}}_{h-1}+{\mathit {n}}_{h-2}$ ${\ displaystyle = 1 + {\ mathit {n}} _ {h-1} + {\ mathit {n}} _ {h-2}}$ ${\ displaystyle = 1 + {\ mathit {n}} _ {h-1} + {\ mathit {n}} _ {h-2}}$

Această afirmație amintește foarte mult de formula recursivă pentru calcularea secvenței Fibonacci . Este posibil să se demonstreze prin inducție că ${\mathit {n}}_{h}={\mathcal {F}}_{h+3}-1$ ${\ displaystyle {\ mathit {n}} _ {h} = {\ mathcal {F}} _ {h + 3} -1}$ ${\ displaystyle {\ mathit {n}} _ {h} = {\ mathcal {F}} _ {h + 3} -1}$ unde este ${\mathcal {F}}_{h}$ ${\ displaystyle {\ mathcal {F}} _ {h}}$ ${\ displaystyle {\ mathcal {F}} _ {h}}$ reprezintă elementul h al secvenței Fibonacci.

Pasul de bază:

Pasul de bază este verificat în mod banal, având în vedere că ${\mathit {n}}_{0}=1$ ${\ displaystyle {\ mathit {n}} _ {0} = 1}$ ${\ displaystyle {\ mathit {n}} _ {0} = 1}$ Și ${\mathcal {F}}_{3}-1=2-1=1$ ${\ displaystyle {\ mathcal {F}} _ {3} -1 = 2-1 = 1}$ ${\ displaystyle {\ mathcal {F}} _ {3} -1 = 2-1 = 1}$ .

Pas inductiv:

Să presupunem pentru fiecare ${\mathit {k}}<{\mathit {h}}$ ${\ displaystyle {\ mathit {k}} <{\ mathit {h}}}$ ${\ displaystyle {\ mathit {k}} <{\ mathit {h}}}$ avem asta ${\mathit {n}}_{k}={\mathcal {F}}_{k+3}-1$ ${\ displaystyle {\ mathit {n}} _ {k} = {\ mathcal {F}} _ {k + 3} -1}$ ${\ displaystyle {\ mathit {n}} _ {k} = {\ mathcal {F}} _ {k + 3} -1}$ și folosirea recurențelor legate de $n_{h}$ ${\ displaystyle n_ {h}}$ ${\ displaystyle n_ {h}}$ și anunț ${\mathcal {F}}_{i}$ ${\ displaystyle {\ mathcal {F}} _ {i}}$ ${\ displaystyle {\ mathcal {F}} _ {i}}$ primesti:

${\mathit {n}}_{h}=1+{\mathit {n}}_{h-1}+{\mathit {n}}_{h-2}=1+{\mathcal {F}}_{h+2}-1+{\mathcal {F}}_{h+1}-1={\mathcal {F}}_{h+3}-1$ ${\ displaystyle {\ mathit {n}} _ {h} = 1 + {\ mathit {n}} _ {h-1} + {\ mathit {n}} _ {h-2} = 1 + {\ mathcal {F}} _ {h + 2} -1 + {\ mathcal {F}} _ {h + 1} -1 = {\ mathcal {F}} _ {h + 3} -1}$ ${\ displaystyle {\ mathit {n}} _ {h} = 1 + {\ mathit {n}} _ {h-1} + {\ mathit {n}} _ {h-2} = 1 + {\ mathcal {F}} _ {h + 2} -1 + {\ mathcal {F}} _ {h + 1} -1 = {\ mathcal {F}} _ {h + 3} -1}$

De asemenea, o proprietate a secvenței Fibonacci este aceea că raportul a două numere din secvență $\lim _{h\rightarrow \infty }{\frac {{\mathcal {F}}_{h+1}}{{\mathcal {F}}_{h}}}$ ${\ displaystyle \ lim _ {h \ rightarrow \ infty} {\ frac {{\ mathcal {F}} _ {h + 1}} {{\ mathcal {F}} _ {h}}}}$ ${\ displaystyle \ lim _ {h \ rightarrow \ infty} {\ frac {{\ mathcal {F}} _ {h + 1}} {{\ mathcal {F}} _ {h}}}}$ este din ce în ce mai aproape de raportul de aur $\phi ={\frac {(1+{\sqrt {5}})}{2}}\approx 1,61803...$ ${\ displaystyle \ phi = {\ frac {(1 + {\ sqrt {5}})} {2}} \ approx 1.61803 ...}$ ${\ displaystyle \ phi = {\ frac {(1 + {\ sqrt {5}})} {2}} \ approx 1.61803 ...}$ și demonstrează că ${\mathcal {F}}_{h}={\frac {\phi ^{h}-(1-\phi )^{h}}{\sqrt {5}}}={\frac {\phi ^{h}-(-\phi )^{-h}}{\sqrt {5}}}=\theta (\phi ^{h})$ ${\ displaystyle {\ mathcal {F}} _ {h} = {\ frac {\ phi ^ {h} - (1- \ phi) ^ {h}} {\ sqrt {5}}} = {\ frac { \ phi ^ {h} - (- \ phi) ^ {- h}} {\ sqrt {5}}} = \ theta (\ phi ^ {h})}$ ${\ displaystyle {\ mathcal {F}} _ {h} = {\ frac {\ phi ^ {h} - (1- \ phi) ^ {h}} {\ sqrt {5}}} = {\ frac { \ phi ^ {h} - (- \ phi) ^ {- h}} {\ sqrt {5}}} = \ theta (\ phi ^ {h})}$ .

Înălțimea arborelui și numărul de noduri sunt, prin urmare, legate în mod exponențial, motiv pentru care se obține $h=\Theta (\log \ n_{h})$ ${\ displaystyle h = \ Theta (\ log \ n_ {h})}$ ${\ displaystyle h = \ Theta (\ log \ n_ {h})}$ , în detaliu un copac Fibonacci cu $n_{h}$ ${\ displaystyle n_ {h}}$ ${\ displaystyle n_ {h}}$ noduri are înălțime $<1,44\ \log(n_{h}+2)-0,328$ ${\ displaystyle <1,44 \ \ log (n_ {h} +2) -0,328}$ ${\ displaystyle <1,44 \ \ log (n_ {h} +2) -0,328}$

Considerații

Lema anterioară ne permite, de asemenea, să dovedim că înălțimea oricărui arbore AVL este o funcție logaritmică a numărului de noduri.

Alte proiecte

Wikimedia Commons conține imagini sau alte fișiere de copac Fibonacci