binomial tree

(data structure)

Definition: An ordered tree of order k ≥ 0, that is Bk, whose root has k children where the ith child is binomial tree of order k-i.

See also binomial heap.

Note: A Bk tree has 2k 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

More information

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: