Біноміальне дерево

Біноміальне дерево (англ. binomial tree) B_k — це рекурсивно означене упорядковане дерево. Біноміальне дерево B₀ складається з одного вузла. Біноміальне дерево B_k складається з двох біноміальних дерев B_k-1 з'єднаних разом: корінь одного з них є крайнім лівим дочірнім вузлом кореня другого дерева. Біноміальні дерева використовуються як частини біноміальної купи.

Біноміальне дерево B_k

1. має 2^k вузлів;
2. має висоту k;
3. має рівно ${\displaystyle {k \choose i}}$ вузлів на глибині ${\displaystyle i=0,1,...,k}$
4. має корінь ступіня k; ступінь всіх інших вершин менша ступіня кореня біноміального дерева. Крім того, якщо дочірні вузли пронумерувати зліва направо числами k - 1, k - 2, …, 0, то i-ий дочірній вузол кореня є коренем біноміального дерева B_i.

Термін «біноміальне дерево» походить з властивості 3, оскільки ${\displaystyle {k \choose i}}$ є біноміальними коефіцієнтами.

• Java applet simulation of binomial heap
• Python implementation of binomial heap [Архівовано 13 травня 2007 у Wayback Machine.]
• Two C implementations of binomial heap [Архівовано 1 липня 2020 у Wayback Machine.] (a generic one and one optimized for integer keys)
• Haskell implementation of binomial heap [Архівовано 4 березня 2012 у Wayback Machine.]
• Common Lisp implementation of binomial heap [Архівовано 5 вересня 2020 у Wayback Machine.]