Двоичные деревья: виды и спецификация

Модуль "Деревья" • урок 2 из 11 • ~6 минут

Отличие от деревьев общего вида

Бинарное (двоичное) дерево - это конечное множество узлов, которое или пусто, или состоит из корня и двух непересекающихся поддеревьев (левого и правого).

Два важнейших отличия бинарного дерева от дерева общего вида:

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

Двоичные деревья: строгие, полные и совершенные

В программировании и анализе алгоритмов выделяют три важных подвида двоичных деревьев:

• Строго бинарное дерево (Strictly Binary Tree): Каждая вершина имеет ровно 0 или 2 поддерева. Вершин с одним сыном не существует.
• Полное бинарное дерево (Complete Binary Tree): Заполнены все уровни, кроме, возможно, последнего. Последний уровень заполняется строго слева направо (без "дырок"). Именно это свойство позволяет легко реализовать структуру "Куча" (Heap) на обычных массивах для алгоритма пирамидальной сортировки.
• Совершенное бинарное дерево (Perfect Binary Tree): Полностью заполненный идеальный треугольник. Все внутренние узлы имеют по 2 сына, все листья находятся строго на одной максимальной глубине. Количество узлов всегда равно 2h - 1, где h - глубина дерева.

Функциональная спецификация

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

Базовый набор операций спецификации:

• СОЗДАТЬ(v, L, R) - конструирует новое дерево, корнем которого будет элемент v, левым поддеревом - дерево L, а правым - дерево R. Дерево собирается "снизу вверх".
• ПУСТО(T) - предикат, проверяющий, является ли дерево T пустым.
• КОРЕНЬ(T) - возвращает значение корневого узла дерева T.
• ЛЕВОЕ_ПОДДЕРЕВО(T) / ПРАВОЕ_ПОДДЕРЕВО(T) - возвращает левую или правую ветвь как самостоятельное целое поддерево.

Для этих операций задаются логические аксиомы:

• ПУСТО( СОЗДАТЬ(v, L, R) ) = Ложь (созданное дерево никогда не пусто).
• КОРЕНЬ( СОЗДАТЬ(v, L, R) ) = v (селектор корня извлекает переданное значение).
• ЛЕВОЕ_ПОДДЕРЕВО( СОЗДАТЬ(v, L, R) ) = L.

Интерфейс на C

Перевод функциональной спецификации на язык C выглядит как интерфейс, описывающий абстрактный тип данных. Само физическое устройство Tree скрыто от программиста, использующего этот интерфейс:

#include <stdbool.h>

typedef int Data;
typedef struct Tree Tree; // Скрытая (непрозрачная) реализация структуры

// Интерфейс, отражающий функциональную спецификацию:
Tree* MakeTree(Data v, Tree* left, Tree* right); 
bool IsEmpty(Tree* t);                           
Data GetRootData(Tree* t);                       
Tree* GetLeftSubtree(Tree* t);                   
Tree* GetRightSubtree(Tree* t);                  
void DestroyTree(Tree* t);