(data structure)

**Definition:**
An *ordered tree* of *order* k ≥ 0, that is B_{k}, whose *root* has k *children* where the i^{th} child is binomial tree of order k-i.

**See also**
*binomial heap*.

*Note:
A B _{k} tree has 2^{k} nodes, the height is k, and there are k choose i nodes at depth i. *

* Adapted from [CLR90, pages 401 and 402]. CLR90 numbers the children k-1, k-2, ..., 0, making child i a binomial tree of order i. This definition numbers the children from 1 to k. *

Author: PEB

Binomial heap in Wikipedia.

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 9 August 2007.

HTML page formatted Mon Feb 2 13:10:39 2015.

Cite this as:

Paul E. Black, "binomial tree", in
*Dictionary of Algorithms and Data Structures* [online], Vreda Pieterse and Paul E. Black, eds. 9 August 2007. (accessed TODAY)
Available from: http://www.nist.gov/dads/HTML/binomialtree.html