binomial tree

(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

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: http://www.nist.gov/dads/HTML/binomialtree.html