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.