Полное бинарное дерево

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

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

Формально, полное бинарное дерево (complete binary tree) — это бинарное дерево, которое удовлетворяет следующим условиям:

1. Все уровни, кроме, возможно, последнего, полностью заполнены узлами.
2. На последнем уровне все узлы находятся как можно левее (то есть отсутствуют «пробелы» между узлами слева направо).

Из этого определения вытекают важные свойства:

• Высота и количество узлов: Высота полного бинарного дерева с \( n \) узлами равна \( \lfloor \log_2 n \rfloor \). Это минимально возможная высота для бинарного дерева с заданным количеством узлов, что делает его сбалансированным.
• Нумерация узлов: Узлы полного бинарного дерева можно однозначно пронумеровать в порядке обхода в ширину (уровень за уровнем, слева направо). Для узла с индексом \( i \) (начиная с 1) его левый потомок имеет индекс \( 2i \), а правый — \( 2i + 1 \). Это свойство лежит в основе эффективной реализации кучи (heap) в виде массива.
• Количество листьев: В полном бинарном дереве количество листьев может варьироваться от \( 2^{h-1} \) до \( 2^h - 1 \), где \( h \) — высота дерева (количество уровней, считая корень за уровень 1).

Отличие от других типов бинарных деревьев

Полное бинарное дерево часто путают с другими типами, поэтому важно различать:

• Идеальное бинарное дерево (perfect binary tree): Все уровни полностью заполнены. Каждый узел имеет ровно двух потомков, а все листья находятся на одном уровне. Идеальное дерево — частный случай полного дерева, но не наоборот.
• Почти полное бинарное дерево (almost complete binary tree): Синоним полного бинарного дерева. Термин «почти полное» подчеркивает, что последний уровень может быть заполнен не полностью, но все узлы на нём выровнены влево.
• Строгое бинарное дерево (strictly binary tree): Каждый узел имеет либо 0, либо 2 потомка. Полное дерево является строгим, если на последнем уровне нет узлов с одним потомком. Однако полное дерево может содержать узлы только с левым потомком (правый отсутствует), что делает его нестрогим.
• Сбалансированное бинарное дерево (balanced binary tree): Высота левого и правого поддеревьев для каждого узла отличается не более чем на 1. Полное дерево всегда сбалансировано, но не наоборот (например, AVL-дерево может быть сбалансированным, но не полным).

Способы представления

Полное бинарное дерево можно представить двумя основными способами:

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

Благодаря свойству нумерации узлов, полное бинарное дерево может быть эффективно реализовано с помощью массива. Корень хранится в первом элементе (индекс 1). Для узла с индексом \( i \):

• Левый потомок: \( 2i \)
• Правый потомок: \( 2i + 1 \)
• Родитель: \( \lfloor i/2 \rfloor \)

Этот способ крайне эффективен по памяти, так как не требует хранения указателей на потомков, и позволяет быстро вычислять адреса узлов. Он широко используется в реализации двоичной кучи (binary heap) и алгоритмах сортировки (пирамидальная сортировка).

Представление в виде связного списка

Каждый узел представляет собой объект, содержащий данные и указатели на левого и правого потомка. Этот способ более гибкий, но требует больше памяти из-за хранения указателей. Для полного дерева такое представление избыточно, так как массив обеспечивает более компактное хранение.

Применение

Полное бинарное дерево является фундаментальной структурой, лежащей в основе многих алгоритмов и систем:

• Куча (Heap): Двоичная куча (min-heap или max-heap) реализуется именно как полное бинарное дерево. Это обеспечивает логарифмическую сложность операций вставки и удаления максимального (или минимального) элемента.
• Пирамидальная сортировка (Heapsort): Алгоритм сортировки, использующий кучу. Сначала из массива строится полное бинарное дерево (куча), затем из него последовательно извлекаются максимальные элементы.
• Очереди с приоритетом: Реализация очередей с приоритетом, где элемент с наивысшим приоритетом всегда находится в корне кучи.
• Деревья отрезков (Segment Tree): В некоторых реализациях деревьев отрезков, особенно при работе с массивами фиксированного размера, используется представление, близкое к полному бинарному дереву.
• Кодирование Хаффмана: Дерево Хаффмана, используемое для сжатия данных, является полным бинарным деревом (все узлы имеют 0 или 2 потомка, а листья — кодируемые символы). Однако оно не обязательно является полным в смысле заполнения уровней слева направо.
• Алгоритмы поиска: Хотя полное дерево не является деревом поиска (BST) по своей сути, оно может быть использовано для построения сбалансированных структур данных, таких как B-деревья, где важна минимизация высоты.

Примеры

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

`` A / \ B C / \ / D E F `` В этом дереве уровни 1 и 2 полностью заполнены. На третьем уровне есть три узла (D, E, F), и они расположены максимально левее. Узел C имеет только левого потомка (F), что допустимо для полного дерева.

Пример 2: Неполное дерево

`` A / \ B C / \ \ D E F `` В этом дереве на третьем уровне есть пробел: узел C имеет только правого потомка (F), а левый потомок отсутствует. Узлы не выровнены слева, поэтому это дерево не является полным.

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

• Понятие полного бинарного дерева тесно связано с понятием «двоичного представления» чисел. Номер узла в массиве соответствует его позиции в дереве.
• В информатике полные бинарные деревья часто используются в качестве модели для анализа сложности алгоритмов «разделяй и властвуй», так как они обеспечивают минимальное количество операций для обработки данных.
• Термин «полное» (complete) в русскоязычной литературе иногда путают с «идеальным» (perfect). В англоязычной литературе это различие более строгое: complete binary tree — полное, perfect binary tree — идеальное.

Источники

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