Біноміальне дерево
Матеріал з Вікіпедії — вільної енциклопедії.
Біноміальне дерево (англ. binomial tree) Bk — це рекурсивно означене упорядковане дерево. Біноміальне дерево B0 складається з одного вузла. Біноміальне дерево Bk складається з двох біноміальних дерев Bk-1 з'єднаних разом: корінь одного з них є крайнім лівим дочірнім вузлом кореня другого дерева. Біноміальні дерева використовуються як частини біноміальної купи.
[ред.] Властивості біноміальних дерев
Біноміальне дерево Bk
- має 2k вузлів;
- має висоту k;
- має рівно
вузлів на глибині i = 0,1,...,k
- має корінь ступіня k; ступінь всіх інших вершин менша ступіня кореня біноміального дерева. Крім того, якщо дочірні вузли пронумерувати зліва направо числами k- 1, k - 2,...,0, то i-ий дочірній вузол кореня є корнем біноміального дерева Bi.
[ред.] Походження терміну
Термін „біноміальне дерево“ походить з властивості 3, оскільки є біноміальними коефіцієнтами.