Полное двоичное дерево¶

Полное двоичное дерево — это структура данных, представляющая собой двоичное дерево, в котором каждый узел имеет ровно 0 или 2 потомка (дочерних узла). В отличие от полного двоичного дерева, где все уровни, кроме последнего, полностью заполнены, полное двоичное дерево не требует обязательного заполнения последнего уровня слева направо. Основное свойство такого дерева — отсутствие узлов с одним потомком, что обеспечивает определённые баланс и симметрию структуры. Полные двоичные деревья широко применяются в информатике, в частности, в теории кодирования, построении кодов Хаффмана и реализации куч (heap).

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

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

• Каждый узел имеет либо 0 потомков (является листом), либо 2 потомка (является внутренним узлом).
• Не существует узлов с ровно одним потомком.

Это свойство накладывает ограничения на структуру дерева. Например, в полном двоичном дереве количество листьев всегда на единицу больше количества внутренних узлов. Если обозначить число внутренних узлов как \(i\), а число листьев как \(l\), то выполняется соотношение: \(l = i + 1\). Это следует из того, что в любом двоичном дереве количество рёбер равно \(n - 1\), где \(n\) — общее число узлов, а каждый внутренний узел добавляет два ребра к потомкам.

Другие важные свойства:

• Высота полного двоичного дерева с \(n\) узлами лежит в диапазоне от \(\lceil \log_2(n+1) \rceil\) до \(n/2\) (в худшем случае, когда дерево вырождено в «цепочку» из внутренних узлов с двумя листьями на каждом уровне).
• Минимальное количество узлов в полном двоичном дереве высоты \(h\) равно \(2h + 1\) (один корень и \(h\) уровней с двумя узлами на каждом, кроме последнего, где два листа). Максимальное количество узлов — \(2^{h+1} - 1\) (полное дерево, где все уровни заполнены).

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

В теории двоичных деревьев существует несколько близких, но различных понятий:

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

Таким образом, полное двоичное дерево — это более общее понятие, чем идеальное, но более узкое, чем произвольное двоичное дерево.

¶История

Понятие полного двоичного дерева возникло в контексте развития теории графов и структур данных в середине XX века. Одним из ранних применений стало использование таких деревьев в алгоритмах кодирования, в частности, в коде Хаффмана, разработанном Дэвидом Хаффманом в 1952 году. В коде Хаффмана строится полное двоичное дерево, где листья соответствуют символам алфавита, а внутренние узлы — результатам объединения частот. Это свойство обеспечивает оптимальность префиксного кода.

В 1960-х годах полные двоичные деревья стали использоваться в реализации двоичных куч (binary heap), предложенных Дж. Уильямсом для алгоритма пирамидальной сортировки (heapsort). В куче дерево должно быть полным (complete), но не обязательно полным (full), однако в некоторых вариантах, например, в левосторонних кучах, используется полное дерево.

¶Классификация и примеры

Полные двоичные деревья можно классифицировать по различным признакам:

• По высоте: минимальные (с минимальным числом узлов при заданной высоте) и максимальные (полностью заполненные, то есть идеальные).
• По способу хранения: в памяти компьютера полные деревья часто хранятся в виде массива, где для узла с индексом \(i\) левый потомок находится по индексу \(2i+1\), а правый — по \(2i+2\). Это удобно для полных деревьев, но для полных (full) такое представление менее эффективно, так как может содержать пустые ячейки.

Примеры:

• Дерево с корнем, имеющим два листа: это простейшее полное двоичное дерево высоты 1 (3 узла).
• Дерево, где корень имеет двух потомков, каждый из которых является листом: 3 узла, высота 1.
• Дерево высотой 2: корень, два внутренних узла (каждый с двумя листьями) — всего 7 узлов (идеальное дерево).
• Дерево, где корень имеет два потомка, левый потомок — внутренний узел с двумя листьями, а правый — лист: такое дерево не является полным, так как правый потомок корня имеет только один потомок (ноль, но это лист, а не внутренний узел). Однако это полное дерево? Нет, так как правый потомок корня — лист, а левый — внутренний узел, но корень имеет двух потомков, и каждый из них имеет либо 0, либо 2 потомка. Левый потомок имеет 2 потомка, правый — 0, поэтому условие выполняется. Это полное дерево высоты 2 с 5 узлами (корень, два внутренних узла? Нет: корень — внутренний, левый потомок — внутренний, его два потомка — листья, правый потомок — лист. Итого: корень, левый внутренний, два листа слева, один лист справа — 5 узлов, из них 2 внутренних, 3 листа. Соотношение \(l = i + 1\) выполняется.

¶Применение

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

¶Коды Хаффмана

В алгоритме Хаффмана для сжатия данных строится полное двоичное дерево, где каждый внутренний узел представляет собой объединение двух символов с наименьшими частотами. Это гарантирует, что ни один код не является префиксом другого (префиксное свойство), и обеспечивает минимальную среднюю длину кода.

¶Двоичные кучи

Хотя классическая двоичная куча (binary heap) обычно реализуется как полное (complete) дерево, в некоторых вариантах, таких как левосторонние кучи (leftist heap) или скошенные кучи (skew heap), используется полное (full) дерево. В левосторонних кучах каждый узел имеет 0 или 2 потомка, что упрощает операции слияния.

¶Деревья решений

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

¶Теория графов

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

¶Алгоритмические аспекты

Работа с полными двоичными деревьями включает операции обхода, вставки и удаления узлов. Обходы (в глубину: прямой, симметричный, обратный; в ширину) выполняются стандартными способами. Вставка нового узла в полное дерево возможна только путём замены листа на внутренний узел с двумя листьями, что сохраняет свойство полноты. Удаление узла, наоборот, может потребовать слияния двух листьев в один.

Для проверки, является ли дерево полным, можно использовать рекурсивный алгоритм: для каждого узла проверяется, что количество потомков равно 0 или 2, и что это свойство выполняется для всех поддеревьев.

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

• В полном двоичном дереве количество листьев всегда нечётно, если число внутренних узлов целое. Из соотношения \(l = i + 1\) следует, что общее число узлов \(n = i + l = 2i + 1\) нечётно.
• Любое полное двоичное дерево является также двоичным деревом, но не наоборот. Например, вырожденное дерево (каждый узел имеет одного потомка) не является полным.
• В русскоязычной литературе термин «полное двоичное дерево» иногда путают с «полным двоичным деревом» (complete), что может вызывать неоднозначность. В англоязычной терминологии различие чёткое: full binary tree — полное, complete binary tree — полное (заполненное).

¶Источники

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