NIST

Fibonacci tree

(data structure)

Definition: A variant of a binary tree where a tree of order n (n>1) has a left subtree of order n-1 and a right subtree of order n-2. An order 0 Fibonacci tree has no nodes, and an order 1 tree has 1 node.

Generalization (I am a kind of ...)
binary tree, AVL tree.

Aggregate parent (I am a part of or used in ...)
Fibonaccian search.

Aggregate child (... is a part of or used in me.)
Fibonacci number.

Note: A Fibonacci tree of order n has F(n+2)-1 nodes, where F(n) is the nth Fibonacci number. A Fibonacci tree is the most unbalanced AVL tree allowed.

Author: PEB

More information

[Knuth98, 3:417, Sect. 6.2.1].


Go to the Dictionary of Algorithms and Data Structures home page.

If you have suggestions, corrections, or comments, please get in touch with Paul Black.

Entry modified 4 January 2010.
HTML page formatted Mon Feb 2 13:10:39 2015.

Cite this as:
Paul E. Black, "Fibonacci tree", in Dictionary of Algorithms and Data Structures [online], Vreda Pieterse and Paul E. Black, eds. 4 January 2010. (accessed TODAY) Available from: http://www.nist.gov/dads/HTML/fibonacciTree.html