(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 n ^{th} Fibonacci number. A Fibonacci tree is the most unbalanced AVL tree allowed.*

Author: PEB

[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 E. Black.

Entry modified 4 January 2010.

HTML page formatted Fri Mar 25 16:20:34 2011.

Cite this as:

Paul E. Black, "Fibonacci tree", in
*Dictionary of Algorithms and Data
Structures* [online], Paul E. Black, ed.,
U.S. National Institute of
Standards and Technology. 4 January 2010. (accessed TODAY)
Available from: http://www.nist.gov/dads/HTML/fibonacciTree.html