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

Матеріал з Вікіпедії — вільної енциклопедії.

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

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

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

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

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

[ред.] Походження терміну

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

Іншими мовами