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 11 February 2019.
HTML page formatted Wed Mar 13 12:42:45 2019.

Cite this as:
Paul E. Black, "binomial tree", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed. 11 February 2019. (accessed TODAY) Available from: https://www.nist.gov/dads/HTML/binomialtree.html