Java 9 Data Structures and Algorithms

Binomial forest

A binomial forest is a very interesting data structure. But, to discuss it, we need to first start with a binomial tree. A binomial tree is a tree in which a combination of two smaller binomial trees of the same size are combined in a particular way:

Binomial tree

The preceding figure shows how binomial trees combine to create larger binomial trees. In the first row, two binomial trees of height 1 combine to create a new binomial tree of height 2. In the second row, two binomial trees of height 2 combine to create a new binomial tree of height 3. In the final example, two binomial trees of height 3 combine to create a binomial tree ...