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

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

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

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

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

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

Походження терміна

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

Посилання

• Java applet simulation of binomial heap
• Python implementation of binomial heap Шаблон:Webarchive
• Two C implementations of binomial heap Шаблон:Webarchive (a generic one and one optimized for integer keys)
• Haskell implementation of binomial heap Шаблон:Webarchive
• Common Lisp implementation of binomial heap Шаблон:Webarchive