Строгое бинарное дерево¶

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

¶Определение и формальные свойства

Строгое бинарное дерево является частным случаем бинарного дерева. В отличие от общего бинарного дерева, где узел может иметь 0, 1 или 2 потомка, в строгом бинарном дереве количество потомков для каждого узла строго фиксировано: либо 0 (лист), либо 2 (внутренний узел). Это свойство накладывает определённые ограничения на структуру дерева.

Ключевые свойства строгого бинарного дерева:

• Количество листьев и внутренних узлов: В любом непустом строгом бинарном дереве количество листьев (L) всегда на единицу больше количества внутренних узлов (I). Формула: L = I + 1. Это следует из того, что каждый внутренний узел добавляет два ребра, а общее количество рёбер в дереве равно общему количеству узлов минус один.
• Высота и количество узлов: Минимальная высота строгого бинарного дерева с n узлами составляет примерно log₂(n+1) – 1, а максимальная — (n-1)/2. Высота измеряется как количество рёбер на пути от корня до самого глубокого листа.
• Связь с полным бинарным деревом: В русскоязычной литературе термин «строгое бинарное дерево» часто используется как синоним «полного бинарного дерева» (в одном из определений). В англоязычной терминологии для этого понятия чаще применяется термин «full binary tree», в то время как «complete binary tree» обозначает дерево, все уровни которого, кроме, возможно, последнего, полностью заполнены, а узлы на последнем уровне располагаются слева направо.

¶Классификация и виды

Строгие бинарные деревья можно классифицировать по нескольким признакам, хотя они сами по себе являются подклассом бинарных деревьев.

¶По структуре

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

¶По способу представления

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

¶Применение

Строгие бинарные деревья находят широкое применение в различных областях компьютерных наук и программирования.

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

Двоичная куча (binary heap) — это структура данных, реализованная на основе полного строгого бинарного дерева. Она используется для реализации приоритетных очередей. В двоичной куче каждый узел имеет значение, которое не меньше (в max-куче) или не больше (в min-куче) значений его потомков. Операции вставки и удаления максимального/минимального элемента выполняются за O(log n).

¶Деревья поиска

Строгие бинарные деревья могут быть использованы для построения деревьев бинарного поиска (BST), хотя в общем случае BST не обязано быть строгим. Однако, в некоторых реализациях, таких как красно-чёрные деревья, свойство строгости может быть выполнено. Красно-чёрные деревья (Red-Black Trees) — это самобалансирующиеся бинарные деревья поиска, которые гарантируют логарифмическую высоту. В них каждый узел помечается как красный или чёрный, и накладываются ограничения, обеспечивающие балансировку. Хотя красно-чёрные деревья не обязательно являются строгими, они часто используются в качестве основы для реализации ассоциативных массивов.

¶Кодирование Хаффмана

Алгоритм Хаффмана для сжатия данных без потерь строит оптимальное префиксное кодирование на основе частот символов. Результатом работы алгоритма является строгое бинарное дерево, в котором каждый лист соответствует символу, а путь от корня до листа определяет его код. Свойство строгости гарантирует, что ни один код не является префиксом другого, что позволяет однозначно декодировать сообщение.

¶Представление арифметических выражений

Строгие бинарные деревья используются для представления арифметических выражений. В таком дереве внутренние узлы соответствуют операторам (+, -, *, /), а листья — операндам (числам или переменным). Это позволяет эффективно вычислять значение выражения, а также выполнять его символьное дифференцирование или упрощение.

¶Генетические алгоритмы

В генетических алгоритмах строгие бинарные деревья могут использоваться для представления хромосом, особенно в генетическом программировании. Каждое дерево кодирует некоторую программу или математическое выражение, а операции скрещивания и мутации выполняются путём обмена поддеревьями.

¶Примеры

¶Пример 1: Двоичная куча

Рассмотрим массив [10, 9, 8, 7, 6, 5, 4]. Если представить его в виде полного строгого бинарного дерева, то корнем будет 10, его левым потомком — 9, правым — 8, и так далее. Это дерево является строгим, так как каждый узел имеет 0 или 2 потомка, и все уровни, кроме последнего, заполнены.

¶Пример 2: Дерево Хаффмана

Пусть есть символы A, B, C, D с частотами 5, 4, 3, 2. Алгоритм Хаффмана построит строгое бинарное дерево, где корень будет иметь вес 14, его левый потомок — вес 9 (содержит A и B), правый — вес 5 (содержит C и D). Коды: A — 00, B — 01, C — 10, D — 11.

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

• Строгие бинарные деревья тесно связаны с числами Каталана. Количество различных строгих бинарных деревьев с n листьями равно (n-1)-му числу Каталана. Например, для 3 листьев существует 2 различных строгих бинарных дерева, для 4 листьев — 5.
• В теории графов строгое бинарное дерево является примером регулярного графа, но не в полном смысле, так как степень корня может быть 2, а листьев — 1.
• Понятие строгого бинарного дерева используется в математической логике для представления формул в виде синтаксических деревьев.

¶Источники

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