Binomial Trees

Binomial trees are the building blocks of binomial heaps. They are defined recursively and have a precise combinatorial structure that makes merging two heaps analogous to binary addition.

Recursive Definition

A binomial tree $B_k$ of order $k$ is defined:

• $B_0$: a single node (the root, degree 0)
• $B_k$ ($k \ge 1$): formed by taking two $B_{k-1}$ trees and making the root of one the leftmost child of the root of the other

$B_0$: one node. $B_1$: root with one child (two $B_0$ trees). $B_2$: root with two children (two $B_1$ trees merged). $B_3$: root with three children (two $B_2$ trees merged).

Properties (Proof by Induction)

For $B_k$:

Property	Value	Induction
Number of nodes	$2^k$	Base: $B_0$ has 1. Step: $2 \cdot 2^{k-1} = 2^k$
Height	$k$	Base: $B_0$ height 0. Step: $1 + (k-1) = k$
Root degree	$k$	Root has $k$ children (greater than any other node)
Nodes at depth $d$	$\binom{k}{d}$	Follows from recursive structure (Pascal’s triangle)
Children of root	$B_{k-1}, B_{k-2}, \ldots, B_0$	From left to right, by construction

Depth Distribution

The binomial coefficient property gives the tree its name. The number of nodes at depth $d$ in $B_k$ is $\binom{k}{d}$. This can be verified for small $k$:

• $B_3$: depth 0: $\binom{3}{0} = 1$, depth 1: $\binom{3}{1} = 3$, depth 2: $\binom{3}{2} = 3$, depth 3: $\binom{3}{3} = 1$
• Total nodes: $1 + 3 + 3 + 1 = 8 = 2^3$ ✓

Maximum Degree

Since $B_k$ has $2^k$ nodes and root degree $k$, the maximum degree of any node in a binomial tree with $n$ nodes is $\le \log_2 n$. This bounds the height of bubble-up and bubble-down operations.

Heap Ordering

A binomial tree is heap-ordered if the key of each node is $\le$ the key of each of its children (min-heap property). Since children are $B_{k-1}, \ldots, B_0$ subtrees, this property must hold recursively.

When merging two heap-ordered $B_k$ trees, the root with the larger key becomes a child of the root with the smaller key. This preserves the heap property in $O(1)$ time.

Binary Representation Connection

A binomial heap with $N$ items is a collection of binomial trees with distinct orders. The orders present correspond to the 1-bits in the binary representation of $N$.

Example: $N = 13 = 1101_2 = 8 + 4 + 1 = 2^3 + 2^2 + 2^0$. The heap contains $B_3$ (8 nodes), $B_2$ (4 nodes), and $B_0$ (1 node).

This binary structure is what makes merging two heaps analogous to binary addition (see Binomial Heap Structure).

Summary

$B_k$ property	Value
Nodes	$2^k$
Height	$k$
Root degree	$k$ (maximum in tree)
Depth $d$ nodes	$\binom{k}{d}$
Root’s children	$B_{k-1}, B_{k-2}, \ldots, B_0$
Max degree ($n$ nodes)	$\le \log_2 n$

Past Tripos: y2024p2q7, y2023p1q9.