Binomial Tree

PAL Definice Binomiální strom

Recursively defined as following:

• Binomial tree of order 0 is a single node.
• Binomial tree of order $k$ is made of two trees of order $k-1$. Tree with lesser key in root has the second tree linked as descendant.

Alternatively:

• Binomial tree of order 0 is a single node.
• Binomial tree of order $k$ is made of a new node with trees of order $0,1$, $2$, $\dots$, $k-1$ linked as descendants in that order

Properties

k-order binomial tree has

• $2^k$ nodes
• $\left(\genfrac{}{}{0ex}{}{k}{i}\right)$ nodes in the $i$-th level
• depth $k$