Расширенные бинарные деревья

В заключение рассмотрим полезные свойства строго бинарных деревьев (в таких деревьях каждый внутренний узел содержит ровно двух сыновей). Ранее было доказано, что количество листьев в полном бинарном дереве ровно на единицу больше количества внутренних узлов. Можно показать, что данное утверждение справедливо для любого строго бинарного дерева, не обязательно полного. Действительно, пусть количество листьев равно L, а количество внутренних узлов — S. Тогда число ветвей, исходящих из всех внутренних узлов, равно 2S (дерево строго бинарное). Общее количество ветвей дерева на единицу меньше числа узлов и составляет L+S-1 (в каждый узел дерева, кроме корня, входит ровно одна ветвь). Следовательно, 2S=L+S-1, отсюда L=S+1, а общее количество узлов строго бинарного дерева n=2L-1.

Этими полезными свойствами строго бинарных деревьев можно  воспользоваться и для анализа обычных бинарных деревьев. Для этого бинарное дерево дополняют фиктивными внешними узлами так, чтобы каждая ветвь дерева заканчивалась таким фиктивным узлом. При таком дополнении любое бинарное дерево превращается в строго бинарное и называется расширенным бинарным деревом. Пример изображения расширенного бинарного дерева изображен на рис. 3.10, при этом фиктивные листья показаны прямоугольниками.

Рис. 3.10. Расширенное бинарное дерево

Деревья как АТД

Аналогично другим структурам данных, таким как линейные и иерархические списки, можно ввести понятия АТД «Дерево», «Лес» и «Бинарное дерево», представив формальную функциональную спецификацию. Однако в данном случае положение осложняется двумя обстоятельствами.

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

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

АТД «Дерево» и «Лес»

Рассмотрим функциональную спецификацию структуры данных дерева c узлами типа α: Tree (α). При этом лес деревьев Forest (Tree (α)) определим как L _ list (Tree (α)) через уже известную структуру линейного списка L _ list с базовыми функциями Cons, Head, Tail, Null (см.1.6). Базовые операции с деревом задаются набором функций:

1) Root: Tree ® α;

2) Listing: Tree ® Forest;

3) ConsTree: α Ä Forest ® Tree

и аксиомами, справедливыми для любого u типа α; любого f типа Forest (Tree (α)); любого t типа Tree (α)):

А1) Root (ConsTree (u, f)) = u;

А2) Listing (ConsTree (u, f)) = f;

А3) ConsTree (Root (t), Listing (t)) = t.

Здесь функции Root и Listing - селекторы: Root выделяет корень дерева, а Listing выделяет лес поддеревьев корня данного дерева. Конструктор ConsTree порождает дерево из заданных корня и леса поддеревьев.

АТД «Бинарное дерево»

Далее введем АТД BinTree — сокращенно BT(α), где α — тип данных, которые хранятся в узлах бинарного дерева. Считаем, что значение типа BT есть либо L (пустое бинарное дерево), либо значение типа NonNullBT(α). Тогда базовые операции типа BT (α) задаются набором функций:

0) L: ® BT(α);

1) Root: NonNullBT(α) ® α;

2) Left: NonNullBT (α)® BT(α);

3) Right: NonNullBT ® BT(α);

4) ConsBT: α Ä BT(α) Ä BT(α) ® NonNullBT(α);

5) IsNull: BT(α) ® Boolean;

и набором аксиом, справедливых для всех u типа α, b типа NonNullBT (α), b1, b2 типа BT (α)):

A1) IsNull (L) = true;

A1') IsNull (b) = false;

A2) IsNull (ConsBT (u, b1, b2)) = false;

A3) Root (ConsBT (u, b1, b2)) = u;

A4) Left (ConsBT (u, b1, b2)) = b1;

A5) Right (ConsBT (u, b1, b2)) = b2;

A6) ConsBT (Root (b), Left (b), Right (b)) = b.

Здесь функции Root, Left и Right - селекторы: Root выделяет значение корня бинарного дерева, а Left и Right - его левое и правое поддеревья соответственно. Конструктор ConsBT порождает бинарное дерево из заданных узла и двух бинарных деревьев — его сыновей. Предикат IsNull - индикатор, различающий пустое и непустое бинарные деревья.

Используя рекурсивные вызовы представленных базовых функций, можно реализовать любые действия с бинарными деревьями. Например, дерево, которое изображено на рис. 3.10,а, в следующем разделе будет использоваться как пример для реализации. Если обозначить его t, то можно записать следующее полное левое скобочное представление (для тренировки изобразите дерево, не заглядывая в рисунок):

t=a(b(d (L L) e(g(L L) L)) с(L f(L L)))

Его можно сформировать, используя функцию consbt, следующим образом:

t=consbt(a, consbt(b, consbt(d,L,L),consbt(e,consbt(g,L,L),L)), consbt(c,L,consbt(f,L,L)))

Однако, для того, чтобы добавить или удалить узел (а это типовые операции в большинстве применений деревьев), придется сначала «разобрать» дерево с помощью селекторов, а затем «собрать» с помощью конструктора. Например, для того, чтобы удалить узел g из уже сформированного дерева t, можно использовать следующую последовательность операций

t=consbt(root(t), consbt(root(left(t)), left(left(t), consbt(root(right(left(t))), L,L)), right(t))

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

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