2.4 Результаты тестирования
Пользователь вводит 2 числа любой длины. Затем выбирает операцию.
Результат выполнения различных операций – Рисунок 2,3,4,5
Рисунок
2 – Выполнение операции сложения чисел
Рисунок 3 - Выполнение операции вычитания чисел
Рисунок
4 - Выполнение операции умножения чисел
Рисунок 5 - Выполнение операции деления чисел
3 Задача №3.14
3.1 Постановка задачи и ее анализ
Задача: Дано АВЛ дерево. Удалить элементы заданного промежутка [a,b].
Для решения данной задачи необходимо реализовать процедуру добавления и удаления элементов дерева. При этом нужно учитывать нарушение баланса в АВЛ дереве.
3.2 Описание структур данных
В данной программе необходимо реализовать АВЛ дерево. Описание его структуры представлено ниже:
type
TKey = integer;
TBalance = -1..1;
AVLTree = ^AVLNode;
AVLNode = record
key: TKey;
left, right: AVLTree;
balance: TBalance;
end;
Структура содержит информационное поле key, а также поля left и right – левый правый сыновья. Для удобства создаем также дополнительное поле хранящее баланс дерева.
3.3 Проектирование программы
Создаем следующие процедуры : DelTree(удаление элементов из заданного промежутка), InsertNode(вставка элемента в дерево), Lkp(процедура вывода дерева, прямой обход).
Рассмотрим каждую процедуру.
InsertNode – процедура вставки элемента. Добавление элемента в АВЛ дерево осуществляется как и в двоичное, особенность только в том, что нужно предусмотреть нарушение балансировки в дереве. Поэтому введем логическую переменную, которая определяет добавлен ли элемент, если да, то смотрим поле баланса. Если дисбаланс, тогда смотрим вид дисбаланса: идем по левой и правой ветвям(либо LL, LR; либо RR,RL).
Листинг процедуры InsertNode:
procedure InsertNode(var Tree: AVLTree; const dat: type_data; var flag: boolean);
var node1,node2:AVLTree;
begin
if tree=nil then
begin
new(tree);
flag:=true;
with tree^ do
begin
data:=dat;
left:=nil;
right:=nil;
balance:=0;
end;
end
else
if tree^.data>dat then
begin
InsertNode(tree^.left,dat,flag);
if flag then
case tree^.balance of
1: begin tree^.balance:=0; flag:=false; end;
0: tree^.balance:=-1;
-1: //нарушен баланс
begin
node1:=tree^.left;
if node1^.balance=-1 then //вид дисбаланса LL
begin
tree^.left:=node1^.right;
node1^.right:=tree;
tree^.balance:=0;
tree:=node1;
end
else
//иначе LR
begin
node2:=node1^.right;
node1^.right:=node2^.left;
node2^.left:=node1;
tree^.left:=node2^.right;
node2^.right:=tree;
if node2^.balance=-1 then
tree^.balance:=1
else
tree^.balance:=0;
if node2^.balance=1 then
node1^.balance:=-1
else
node1^.balance:=0;
tree:=node2;
end;
tree^.balance:=0;
flag:=false;
end
end
end
else if tree^.data<dat then
begin
InsertNode(tree^.right,dat,flag);
if flag then
case tree^.balance of
-1: begin tree^.balance:=0; flag:=false; end;
0: tree^.balance:=1;
1: //нарушен баланс
begin
node1:=tree^.right;
if node1^.balance=1 then// вид дисбаланса RR
begin
tree^.right:=node1^.left;
node1^.left:=tree;
tree^.balance:=0;
tree:=node1;
end
else // иначе RL
begin
node2:=node1^.left;
node1^.left:=node2^.right;
node2^.right:=node1;
tree^.right:=node2^.left;
node2^.left:=tree;
if node2^.balance=1 then
tree^.balance:=-1
else
tree^.balance:=0;
if node2^.balance=-1 then
node1^.balance:=1
else
node1^.balance:=0;
tree:=node2;
end;
tree^.balance:=0;
flag:=false
end
end
end
end;
DelTree – удаление происходит как и удаление, например. в списке (перенаправляем указатель). Как и в процедуре добавления элемента смотрим нарушен ли баланс.