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

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

Біноміальні дерева з порядком від 0 до 3: кожне дерево має корінь дочірніми елементами якого є всі біноміальні дерева меншого порядку. Наприклад, біноміальне дерево 3-го порядку складається з дерев порядку 2, 1 і 0(віділені синім, зеленим і червоним відповідно).

Властивості біноміальних дерев

Біноміальне дерево 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}}$ є біноміальними коефіцієнтами.

Посилання

• 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.]