Treba mi opis Fibonacijevog drveta, kao i njegove karakteristike. Da li je u njemu pretraga brza nego u binarnom stablu?
Potpis
Sendvic uvek pada na namazanu stranu!
Fibonacijevo drvo
Zaključano
Zakačeno
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.
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.