Динамические структуры данных. Алексеев А.Ю - 47 стр.

UptoLike

ВУЗ: 

КамчатГТУ | Петропавловск-Камчатский

Составители: 

Рубрика: 

структуры данных, а именно, на базе иерархических списков. Достаточно рас-
сматривать при этом описанное в 3.1 скобочное представление дерева как
S-выражение специальной структуры. Возможно и другое удобное представ-
ление дерева (леса), основанное на некотором соответствии леса и бинарного
дерева, описанном далее в 3.3.
Рассмотрим функциональную спецификацию структуры данных бинарного
дерева с узлами типа α: BinaryTree ( α ) ≡ BT ( α ). Здесь важно различать си-
туации обработки пустого и непустого бинарного дерева, поскольку некото-
рые операции определяются только на непустых бинарных деревьях. Далее
считаем, что значение типа BT есть либо Λ (пустое бинарное дерево), либо
значение типа NonNullBT. Тогда базовые операции типа BT ( α ) задаются на-
бором функций:
1) Root: NonNullBT → α;
2) Left: NonNullBT → BT;
3) Right: NonNullBT → BT;
4) ConsBT: α ⊗ BT ⊗ BT → NonNullBT;
5) Null: BT → Boolean;
6) Λ : → BT
и набором аксиом (∀ u: α, b: NonNullBT ( α ), b1, b2: BT ( α ) ):
A1) Null ( Λ ) = true;
A1') Null ( b ) = false;
A2) Null ( 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 порождает бинарное дерево из заданных узла и двух би-
нарных деревьев. Предикат Null − индикатор, различающий пустое и непустое
бинарные деревья.
3.3. Каноническое соответствие бинарного дерева и леса
Бинарные деревья особенно полезны, в том числе потому, что существует
естественное взаимно однозначное соответствие между лесами и бинарными
деревьями, и многие операции над лесом (деревом) могут быть реализованы
как соответствующие операции над бинарным деревом, представляющим этот
лес (дерево).
Опишем такое представление леса бинарным деревом (и далее будем на-
зывать его каноническим). Пусть лес F типа Forest задан как список деревьев
T
i
типа Tree (для ∀i ∈1..m):
47
структуры данных, а именно, на базе иерархических списков. Достаточно рас-
сматривать при этом описанное в 3.1 скобочное представление дерева как
S-выражение специальной структуры. Возможно и другое удобное представ-
ление дерева (леса), основанное на некотором соответствии леса и бинарного
дерева, описанном далее в 3.3.
   Рассмотрим функциональную спецификацию структуры данных бинарного
дерева с узлами типа α: BinaryTree ( α ) ≡ BT ( α ). Здесь важно различать си-
туации обработки пустого и непустого бинарного дерева, поскольку некото-
рые операции определяются только на непустых бинарных деревьях. Далее
считаем, что значение типа BT есть либо Λ (пустое бинарное дерево), либо
значение типа NonNullBT. Тогда базовые операции типа BT ( α ) задаются на-
бором функций:
   1) Root: NonNullBT → α;
   2) Left: NonNullBT → BT;
   3) Right: NonNullBT → BT;
   4) ConsBT: α ⊗ BT ⊗ BT → NonNullBT;
   5) Null: BT → Boolean;
   6) Λ : → BT
и набором аксиом (∀ u: α, b: NonNullBT ( α ), b1, b2: BT ( α ) ):
   A1) Null ( Λ ) = true;
   A1') Null ( b ) = false;
   A2) Null ( 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 порождает бинарное дерево из заданных узла и двух би-
нарных деревьев. Предикат Null − индикатор, различающий пустое и непустое
бинарные деревья.


         3.3. Каноническое соответствие бинарного дерева и леса

    Бинарные деревья особенно полезны, в том числе потому, что существует
естественное взаимно однозначное соответствие между лесами и бинарными
деревьями, и многие операции над лесом (деревом) могут быть реализованы
как соответствующие операции над бинарным деревом, представляющим этот
лес (дерево).
    Опишем такое представление леса бинарным деревом (и далее будем на-
зывать его каноническим). Пусть лес F типа Forest задан как список деревьев
Ti типа Tree (для ∀i ∈1..m):

                                     47

Страницы