Правила роботи з бінарними деревами
Ефективність роботи з БД у вигляді двійкових дерев багато в чому визначається знаннями процедур їх створення і перетворення. Розглянемо ряд процедур, що оперують із двійковими деревами, що описуються структурами виду
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) показує як подвійне перетворення структури БД дозволяє відсортувати вихідний список. На першому етапі вихідний список перетворюється в бінарне дерево. При цьому забезпечується упорядкованість цього дерева. На другому етапі бінарне дерево перетворюється в список, але тому що дерево упорядковане, то і список виходить відсортованим.