Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.

Fibonacijevo drvo

[es] :: Art of Programming :: Fibonacijevo drvo

[ Pregleda: 3772 | Odgovora: 1 ] > FB > Twit

Postavi temu Odgovori

Autor

Pretraga teme: Traži
Markiranje Štampanje RSS

PeraKojotSuperGenije
Sasa Popovic
Beograd

Član broj: 44507
Poruke: 126
*.118.eunet.yu.



Profil

icon Fibonacijevo drvo08.04.2005. u 16:00 - pre 201 meseci
Treba mi opis Fibonacijevog drveta, kao i njegove karakteristike. Da li je u njemu pretraga brza nego u binarnom stablu?
Sendvic uvek pada na namazanu stranu!
 
Odgovor na temu

gpreda
Goran Predovic
Kragujevac

Član broj: 19087
Poruke: 74
*.dialup.sezampro.yu.

Sajt: alas.matf.bg.ac.yu/~mr990..


Profil

icon Re: Fibonacijevo drvo10.04.2005. u 15:49 - pre 201 meseci
Fibonacijevo drvo je binarno drvo dubine (reda) n, kome je levo poddrvo reda n-1, a desno poddrvo reda n-2. Takvo drvo reda n ima F(n+2)-1 cvorova, gde je F(n) n-ti Fibonacijev broj.

Fibonacijevo drvo je specijalni slucaj AVL drveta - balansiranog binarnog drveta. Balansirano binarno drvo je takvo da je za svaki cvor razlika redova izmedju levog i desnog poddrveta najvise jedan.

Pretraga u balansiranom binarnom drvetu je teorijski brza od pretrage u obicnom binarnom drvetu, zato sto je srednje vreme pretrage O(log n) garantovano. Obicno binarno drvo moze biti degenerisano i izgledati kao lista, pa je vreme pretrage u najgorem slucaju O(n).

Kao sto se vidi, Fibonacijevo drvo je 'najmanje balansirano' balansirano binarno drvo.
 
Odgovor na temu

[es] :: Art of Programming :: Fibonacijevo drvo

[ Pregleda: 3772 | Odgovora: 1 ] > FB > Twit

Postavi temu Odgovori

Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.