Біноміальне дерево
Біноміальне дерево (англ. binomial tree) Bk — це рекурсивно означене упорядковане дерево. Біноміальне дерево B0 складається з одного вузла. Біноміальне дерево Bk складається з двох біноміальних дерев Bk-1 з'єднаних разом: корінь одного з них є крайнім лівим дочірнім вузлом кореня другого дерева. Біноміальні дерева використовуються як частини біноміальної купи.
Біноміальні дерева з порядком від 0 до 3: кожне дерево має корінь дочірніми елементами якого є всі біноміальні дерева меншого порядку. Наприклад, біноміальне дерево 3-го порядку складається з дерев порядку 2, 1 і 0(віділені синім, зеленим і червоним відповідно).
Властивості біноміальних дерев
Біноміальне дерево Bk
- має 2k вузлів;
- має висоту k;
- має рівно вузлів на глибині
- має корінь ступіня k; ступінь всіх інших вершин менша ступіня кореня біноміального дерева. Крім того, якщо дочірні вузли пронумерувати зліва направо числами k - 1, k - 2, …, 0, то i-ий дочірній вузол кореня є коренем біноміального дерева Bi.
Походження терміну
Термін «біноміальне дерево» походить з властивості 3, оскільки є біноміальними коефіцієнтами.
Посилання
- Java applet simulation of binomial heap
- Python implementation of binomial heap
- Two C implementations of binomial heap (a generic one and one optimized for integer keys)
- Haskell implementation of binomial heap
- Common Lisp implementation of binomial heap
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.