Биномиальное дерево¶

Биномиальное дерево — это структура данных, относящаяся к классу деревьев, которая представляет собой набор биномиальных деревьев, удовлетворяющих определённым свойствам. Биномиальное дерево степени k (обозначается Bₖ) является рекурсивно определённым деревом, где B₀ состоит из одного узла, а Bₖ образуется из двух биномиальных деревьев степени k-1, соединённых таким образом, что корень одного становится крайним левым дочерним узлом корня другого. Ключевая особенность — число узлов в биномиальном дереве степени k равно 2ᵏ. Биномиальные деревья лежат в основе биномиальной кучи — структуры данных, используемой для реализации очередей с приоритетом.

¶История

Концепция биномиальных деревьев была впервые предложена в 1978 году французским учёным Жаном Вюйлеменом (Jean Vuillemin) в его работе «A Data Structure for Manipulating Priority Queues». Вюйлемен ввёл биномиальные кучи как альтернативу двоичным кучам, предложив более эффективные операции слияния (meld). Название «биномиальное» происходит от того, что число узлов на каждом уровне дерева Bₖ равно биномиальному коэффициенту C(k, i) (где i — номер уровня, начиная с 0). Впоследствии биномиальные деревья и кучи были подробно изучены и популяризированы в работах по алгоритмам и структурам данных, в частности, в книге «Алгоритмы: построение и анализ» Томаса Кормена и соавторов.

¶Свойства биномиальных деревьев

Биномиальное дерево Bₖ обладает следующими свойствами:

• Количество узлов: ровно 2ᵏ.
• Высота: k (глубина от корня до самого удалённого листа).
• Степень корня: k (количество непосредственных дочерних узлов корня равно k).
• Количество узлов на уровне i (где уровень корня — 0, уровень его дочерних узлов — 1 и т.д.): равно биномиальному коэффициенту C(k, i) для 0 ≤ i ≤ k.
• Рекурсивная структура: Bₖ состоит из двух Bₖ₋₁, один из которых является поддеревом корня другого.

Биномиальные деревья являются упорядоченными деревьями, но не обязательно двоичными — каждый узел может иметь произвольное число дочерних узлов, однако структура фиксирована для данной степени.

¶Биномиальная куча

Биномиальная куча — это структура данных, представляющая собой набор (лес) биномиальных деревьев, удовлетворяющих двум основным условиям:

1. Свойство кучи: для каждого узла его ключ (значение) не меньше ключа его родительского узла (в случае min-кучи) или не больше (в случае max-кучи). Обычно рассматриваются min-кучи.
2. Уникальность степеней: в куче не может быть двух биномиальных деревьев одной степени. Это обеспечивается за счёт того, что степени деревьев соответствуют двоичному представлению числа узлов в куче.

Биномиальная куча позволяет эффективно выполнять основные операции над очередями с приоритетом, включая вставку, извлечение минимума, слияние и уменьшение ключа.

¶Операции над биномиальной кучей

• Слияние (meld): объединение двух биномиальных куч в одну. Выполняется за O(log n), где n — общее число узлов. Алгоритм напоминает сложение двоичных чисел: деревья одинаковых степеней сливаются, образуя дерево степени на единицу больше.
• Вставка: добавление нового элемента в кучу. Создаётся биномиальное дерево B₀ из одного узла, которое затем сливается с существующей кучей. Амортизированная сложность — O(1), в худшем случае — O(log n).
• Поиск минимума: минимальный элемент находится среди корней всех деревьев кучи. Сложность — O(log n), так как количество деревьев не превышает log₂(n+1).
• Извлечение минимума: удаление корня с минимальным ключом. После удаления его дочерние узлы (которые сами являются биномиальными деревьями) образуют новую кучу, которая затем сливается с остатком исходной кучи. Сложность — O(log n).
• Уменьшение ключа: изменение значения ключа узла на меньшее (для min-кучи). После изменения может потребоваться восстановление свойства кучи путём перемещения узла вверх (как в двоичной куче). Сложность — O(log n).
• Удаление узла: сначала ключ узла уменьшается до минимально возможного значения (например, -∞), затем выполняется извлечение минимума. Сложность — O(log n).

¶Применение

Биномиальные деревья и кучи находят применение в следующих областях:

• Очереди с приоритетом: биномиальные кучи используются в алгоритмах, требующих частого слияния очередей, например, в алгоритме Прима для построения минимального остовного дерева графа.
• Алгоритм Дейкстры: для поиска кратчайших путей в графах с неотрицательными весами, где требуется эффективное извлечение минимума и уменьшение ключей.
• Симуляция событий: в дискретно-событийных симуляторах, где события обрабатываются в порядке времени.
• Операционные системы: для управления процессами и планирования задач с приоритетами.
• Графические алгоритмы: в некоторых реализациях алгоритма Крускала для поиска минимального остовного дерева.

¶Сравнение с другими структурами данных

Биномиальные кучи занимают промежуточное положение между двоичными кучами и кучами Фибоначчи. Основные отличия:

Биномиальные кучи проще в реализации, чем кучи Фибоначчи, и обеспечивают гарантированно логарифмическое время для всех операций, в отличие от амортизированных оценок у куч Фибоначчи.

¶Реализация

Биномиальное дерево обычно реализуется с помощью узлов, содержащих:

• Ключ (значение).
• Степень (количество дочерних узлов).
• Указатель на родительский узел.
• Указатель на крайнего левого дочернего узла.
• Указатель на правого брата (для организации списка дочерних узлов).

Биномиальная куча представляет собой список корней деревьев, отсортированный по возрастанию степени. Для слияния куч используется вспомогательная процедура, объединяющая два дерева одинаковой степени, сравнивая их корни.

¶Интересные факты

• Название «биномиальное» связано с тем, что число узлов на каждом уровне подчиняется биномиальному распределению, а общее число узлов равно степени двойки.
• Биномиальные деревья тесно связаны с двоичной системой счисления: степени деревьев в куче соответствуют единицам в двоичной записи числа узлов.
• В отличие от двоичных куч, биномиальные кучи не являются полными деревьями, что позволяет более гибко выполнять слияние.

¶Критика

Несмотря на теоретическую эффективность, биномиальные кучи на практике уступают более простым структурам, таким как двоичные кучи, для большинства задач, где не требуется частое слияние. Реализация биномиальных куч сложнее, а накладные расходы на управление указателями могут снижать производительность. Кроме того, для операций, не требующих слияния, двоичные кучи часто оказываются быстрее из-за лучшей локальности данных (использование массива). В современных приложениях, где важна амортизированная производительность, предпочтение отдаётся кучам Фибоначчи или двоичным кучам с оптимизациями.