Почти полное бинарное дерево¶

Почти полное бинарное дерево — это структура данных, представляющая собой бинарное дерево, в котором все уровни, кроме, возможно, последнего, полностью заполнены узлами, а узлы на последнем уровне располагаются максимально влево. Данная структура является промежуточным звеном между полным бинарным деревом и совершенным бинарным деревом, и широко применяется в реализации двоичных куч (binary heaps) и некоторых алгоритмах сортировки.

¶Определение и свойства

В теории графов и информатике бинарное дерево определяется как корневое дерево, в котором каждый узел имеет не более двух дочерних элементов (левого и правого). Почти полное бинарное дерево (англ. almost complete binary tree) удовлетворяет двум условиям:

1. Все уровни, кроме последнего, заполнены полностью (то есть содержат максимально возможное количество узлов — 2^h для уровня h, где h отсчитывается от 0 для корня).
2. На последнем уровне узлы располагаются строго слева направо без пропусков.

Это означает, что при добавлении нового узла он всегда помещается на последний уровень в крайнюю левую свободную позицию. Если последний уровень заполнен полностью, дерево становится совершенным (perfect binary tree), но почти полное дерево может иметь неполный последний уровень.

¶Ключевые характеристики

• Высота: высота почти полного бинарного дерева с n узлами равна ⌊log₂(n)⌋ (округление вниз).
• Количество узлов на уровне: для уровня i (0-индексация) количество узлов равно 2^i, за исключением последнего уровня, где может быть от 1 до 2^h узлов.
• Индексация: при представлении в массиве (например, в куче) узлы нумеруются последовательно: корень — индекс 0, левый дочерний — 2i+1, правый — 2i+2. Для почти полного дерева эта нумерация не содержит пропусков.

¶Отличие от смежных понятий

В литературе часто путают понятия «полное бинарное дерево», «совершенное бинарное дерево» и «почти полное бинарное дерево». Важно различать:

• Полное бинарное дерево (full binary tree): каждый узел имеет 0 или 2 дочерних элемента. Никаких требований к заполнению уровней нет.
• Совершенное бинарное дерево (perfect binary tree): все уровни полностью заполнены. Количество узлов — 2^(h+1) − 1, где h — высота.
• Почти полное бинарное дерево (almost complete binary tree): все уровни, кроме последнего, заполнены, а последний заполняется слева направо. Это подмножество полных деревьев, но не обязательно совершенных.

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

¶Применение

¶Двоичная куча (Binary Heap)

Основное практическое применение почти полного бинарного дерева — реализация двоичной кучи (min-heap или max-heap). Куча — это структура данных, где каждый родительский узел удовлетворяет свойству кучи (например, не больше дочерних для min-heap). Благодаря почти полной структуре, куча может быть эффективно представлена в виде массива без использования указателей, что обеспечивает:

• Вставку элемента за O(log n)
• Удаление корня (экстракция минимума/максимума) за O(log n)
• Построение кучи из массива за O(n)

¶Пирамидальная сортировка (Heapsort)

Алгоритм сортировки Heapsort использует двоичную кучу, построенную на основе почти полного бинарного дерева. Сначала из исходного массива строится куча, затем многократно извлекается корень (максимальный или минимальный элемент) и помещается в конец массива. Временная сложность — O(n log n) в худшем, среднем и лучшем случаях.

¶Приоритетные очереди

Почти полные бинарные деревья лежат в основе многих реализаций приоритетных очередей, где элементы обрабатываются в порядке приоритета. Стандартная библиотека C++ (std::priority_queue), модуль heapq в Python и класс PriorityQueue в Java используют именно эту структуру.

¶Деревья отрезков и другие структуры

В некоторых вариантах деревьев отрезков (segment trees) и деревьев Фенвика (Fenwick tree) также применяется представление в виде почти полного бинарного дерева для упрощения индексации и ускорения операций.

¶Представление в памяти

¶Массив (последовательное хранение)

Наиболее распространённый способ хранения почти полного бинарного дерева — одномерный массив. Узлы располагаются в порядке обхода в ширину (BFS): корень — индекс 0, его левый дочерний — 1, правый — 2, и так далее. Для узла с индексом i:

• Левый дочерний: 2i + 1
• Правый дочерний: 2i + 2
• Родитель: ⌊(i − 1) / 2⌋

Преимущества: компактность (нет накладных расходов на указатели), быстрый доступ по индексу, кэш-локальность. Недостатки: сложность вставки/удаления в середине (не для кучи — для кучи это не требуется).

¶Связное представление (указатели)

Теоретически возможно хранить почти полное бинарное дерево с помощью узлов, содержащих указатели на левого и правого потомка. Однако на практике это неэффективно из-за потери свойства компактности и необходимости дополнительной памяти на указатели. Такое представление используется редко, только если требуется динамическое изменение структуры (например, в некоторых реализациях деревьев поиска).

¶Алгоритмы работы

¶Вставка элемента

Для вставки нового элемента в почти полное бинарное дерево (например, в кучу):

1. Добавить элемент в конец массива (последнюю позицию последнего уровня).
2. Выполнить «просеивание вверх» (sift-up): сравнивать с родителем и при необходимости менять местами, пока не будет восстановлено свойство кучи (или другое заданное условие).

¶Удаление корня

При удалении корневого элемента (экстракции):

1. Заменить корень последним элементом массива (удалить последний узел).
2. Выполнить «просеивание вниз» (sift-down): сравнивать корень с дочерними элементами и менять с наибольшим/наименьшим, пока свойство не восстановится.

¶Построение кучи (heapify)

Построение почти полного бинарного дерева из неупорядоченного массива выполняется за O(n) с помощью процедуры sift-down, применяемой к узлам, начиная с последнего родителя (индекс n/2 − 1) и до корня.

¶Примеры

¶Пример 1: Почти полное дерево с 6 узлами

`` 1 / \ 2 3 / \ 4 5 / 6 `` Уровни: 0 (1 узел), 1 (2 узла), 2 (4 узла — но заполнены только 3, так как последний уровень неполный). Узлы на последнем уровне (6) находятся слева.

¶Пример 2: Представление в массиве

Для дерева из примера 1 массив будет: [1, 2, 3, 4, 5, 6]. Индексы: 0 — корень, 1 — левый дочерний корня, 2 — правый дочерний корня, 3 — левый дочерний узла 2, 4 — правый дочерний узла 2, 5 — левый дочерний узла 4.

¶Пример 3: Не является почти полным

`` 1 / \ 2 3 / \ 4 5 \ 6 `` Узел 6 расположен справа, а не слева на последнем уровне, поэтому дерево не является почти полным.

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

• Термин «почти полное бинарное дерево» ввёл Дональд Кнут в своей книге «Искусство программирования» (том 3, 1973), где он описал связь с кучами.
• В двоичной куче, реализованной на почти полном дереве, высота дерева всегда минимальна для данного количества узлов, что обеспечивает логарифмическую сложность операций.
• Структура почти полного дерева используется в алгоритме Хаффмана (Huffman coding) для построения оптимального префиксного кода, хотя само дерево Хаффмана не обязательно является почти полным.
• В некоторых реализациях B-деревьев (B-trees) также применяется принцип заполнения уровней слева направо для обеспечения сбалансированности.

¶Критика и ограничения

Несмотря на широкое применение, почти полное бинарное дерево имеет ограничения:

• Не подходит для динамических структур, где требуется частая вставка/удаление в произвольные позиции (например, в деревьях поиска), так как поддержание свойства «влево» требует перестройки.
• При представлении в массиве операции вставки и удаления в середине (не на последнем уровне) требуют сдвига элементов, что может быть затратно.
• Для деревьев с большим количеством узлов (миллионы) массив может занимать много памяти, но это компенсируется отсутствием накладных расходов на указатели.

¶Источники

• Кнут Д. Э. Искусство программирования. Том 3. Сортировка и поиск. — 2-е изд. — М.: Вильямс, 2007.
• Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы: построение и анализ. — 3-е изд. — М.: Вильямс, 2013.
• Ахо А., Хопкрофт Дж., Ульман Дж. Структуры данных и алгоритмы. — М.: Вильямс, 2001.
• Седжвик Р. Фундаментальные алгоритмы на C++. Анализ/Структуры данных/Сортировка/Поиск. — СПб.: ДиаСофт, 2002.
• Вирт Н. Алгоритмы и структуры данных. — М.: Мир, 1989.