Правила роботи з бінарними деревами

Ефективність роботи з БД у вигляді двійкових дерев багато в чому визначається знаннями процедур їх створення і перетворення. Розглянемо ряд процедур, що оперують із двійковими деревами, що описуються структурами виду

tree(Left, Root, Right),

де Left – ліве піддерево, кожен елемент якого має структуру, аналогічну tree(), Root – корінь (будь-яка довільна, обумовлена користувачем, структура), Right – праве піддерево, що складається з елементів структури tree().

Побудова бінарного дерева. Задача створення упорядкованого дерева при додаванні деякого елемента Х до впорядкованого дерева може бути сформульована в такий спосіб:

Гранична умова: Додавання Х до порожнього дереву дає tree(end, X, end).

Рекурсивні умови: При включенні Х в tree(Left, Root, Right) треба розглянути два випадки, для того, щоб результуюче дерево було упорядкованим.

1. Якщо Х менше, ніж Root, то Х додається до лівого піддерева.

2. Якщо Х більше, ніж Root, то Х варто додати до правого піддерева.

В обох випадках значення кореня і протилежного піддерева не змінюються. Такому формулюванню відповідає процедура insert(), що має вигляд:

insert(end, X, tree(end, X, end)).

insert(tree(Left, Root, Right ), X, tree(LeftNew, Root, Right)) :- X < Root, insert(Left, X, LeftNew).

insert(tree(Left, Root, Right), X, tree(Left, Root, RightNew)) :- X > Root, insert(Right, X, RightNew).

Побудова бінарного дерева зі списку. Процедуру insert() можна використовувати для побудови впорядкованого дерева зі списку. Процедура, що забезпечує перетворення списку в упорядковане дерево, буде мати вигляд:

list_to_tree([], end).

list_to_tree([H | T], AllTree) :- list_to_tree(T, Tree), insert(Tree, H, AllTree).

Побудова відсортованого списку з дерева. Для рішення цієї задачі можна скористатися упорядкованим бінарним деревом і об'єднанням списків.

Гранична умова: Порожнє бінарне дерево (end) приводить до порожнього списку [].

Рекурсивна умова: Відсортований список для упорядкованого бінарного дерева tree(Left, Root, Right), де Left має відсортований список L1, a Right має відсортований список L2, отримується приєднанням [Root | L2] до L1.

tree_to_list(end,[]).

tree_to_list(tree(Left, Root, Right), List) :- tree_to_list(Left, L1), tree_to_list(Right, L2), append(L1,[Root | L2], List).

Розглянемо приклад використання цих процедур у Пролог-програмі, що працює з базами даних різних структур і перетворення цих структур.

/* Програма 5_2 */

domains

worker = symbol

listworker = worker*

tree = tree(tree, worker, tree); end

predicates

db1(tree)

db2(listworker)

record(worker, tree )

append(listworker, listworker, listworker)

insert(tree, worker, tree)

list_to_tree(listworker, tree)

tree_to_list(tree, listworker)

goal1

goal2

goal3

goal4

goal5

goal6

goal7

goal8

clauses

goal1 :- db1(DB), write(DB).

goal2 :- db1(DB), record(R, DB), write(R), nl, fail.

goal3 :- db1(DB), write(„введіть елемент”), readln(E1), insert(DB, E1, DBnew), write(DBnew).

goal4 :- db1(DB), write(„введіть елемент”), readln(E1), insert(DB, E1, DBnew), record(R, DBnew), write(R), nl, fail.

goal5 :- db2(List), list_to_tree(List, Tree), write(Tree).

goal6 :- db2(List), list_to_tree(List, Tree), record(R, Tree), write(R), nl, fail.

goal7 :- db1(Tree), tree_to_list(Tree,List), write(List).

goal8 :- db2(List), write(List), nl, list_to_tree(List, Tree), write(Tree), nl, tree_to_list(Tree, NewList), write(NewList), nl.

insert(end, X, tree(end, X, end)).

insert(tree(L, Root, R), X, tree(LNew, Root, R)) :- X < Root, insert(L, X, Lnew).

insert(tree(L, Root, R), X, tree(L, Root, RNew)) :- X > Root, insert( R, X, RNew).

list_to_tree([], end).

list_to_tree([H | T], AllTree) :- list_to_tree(T, Tree), insert(Tree, H, AllTree ).

tree_to_list(end,[]).

tree_to_list(tree(L, Root, R), List) :- tree_to_list(L, L1), tree_to_list(R, L2), append(L1,[Root | L2], List).

record(R, tree(LeftTree, _ ,_)):- record( R, LeftTree).

record(R, tree(_, R, _)).

record(R, tree( _, _, RightTree)):- record(R, RightTree).

append([], L2, L3).

append([H | L1], L2,[H | L3]) :- append(L1, L2, L3).

db1(tree(tree(end, a, end), c, tree(end, e, end))).

db2([c, e, a]).

Використання описаних вище процедур дозволяє як модифікувати бази даних, так і здійснювати їхні структурні перетворення. Програма 5_2 дає можливість досліджувати найпростіші перетворення над базами даних. У цій програмі використовуються два способи представлення баз даних: у вигляді списку та у вигляді двійкового дерева. Причому структури цілісних інформаційних елементів обох баз даних прийняті однаковими і, з метою спрощення, містять у собі усього по одному полю символьного типу.

Обидві бази задаються безпосередньо в програмі за допомогою предикатів db1() і db2(). Найпростіші перетворення над базами ілюструються за допомогою восьми цілей, сформованих безпосередньо в програмі. призначення кожної зі сформованих у програмі цілей.

Перша ціль (goal1) дозволяє переглянути вміст першої бази даних, заданої у вигляді бінарного дерева.

Друга ціль (goal2) дозволяє послідовно переглянути записи першої бази даних, що досягається виділенням із БД окремих інформаційних елементів за допомогою процедури record().

Третя і четверта цілі (goal3 і goal4) ілюструють можливість модифікації першої БД шляхом додавання в неї нового елемента зі збереженням упорядкованості.

П'ята і шоста цілі (goal5 і goal6) показують, як база даних, задана у вигляді списку, може бути перетворена в структуру типу бінарного дерева.

Сьома ціль (goal7) ілюструє можливість перетворення впорядкованого дерева у відсортований список.

Восьма ціль (goal8) показує як подвійне перетворення структури БД дозволяє відсортувати вихідний список. На першому етапі вихідний список перетворюється в бінарне дерево. При цьому забезпечується упорядкованість цього дерева. На другому етапі бінарне дерево перетворюється в список, але тому що дерево упорядковане, то і список виходить відсортованим.