Page 45 - 4800

– запис належить дереву, якщо він знаходиться в лівому піддереву,
– запис належить дереву, якщо він є коренем цього дерева,
– запис належить дереву, якщо він знаходиться в правому піддереві.
Цю процедуру, використовуючи синтаксис Прологу, можна описати в такий
спосіб:
record(work(Name, Office, Post, Salary), work4(LeftTree, _,_,_,_, _)):-
record(work(Name, Office, Post, Salary), LetfTree).
record(work(Name, Office, Post, Salary), work4( _, Name, Office, Post, Salary, _)).
record(work(Name, Office, Post, Salary), work4(_, _,_,_,_, RightTree)) :-
record(work(Name, Office, Post, Salary), RightTree).
Тепер процедура record() визначена, і можна написати запит, що дозволяє
знайти всіх службовців відділу 101. Другим аргументом запиту є цілком уся база даних.
Goal: record(work(Name, 101, Post, Salary), work4(work4(end, Денега, 211,
„начальник”, 450, end), „Маслов”, 101, „оператор”, 200, work4(end, „Петренко”, 101,
„менеджер”, 300, end)).
Відповідь на запит буде таж сама, що й у попередніх випадках. Однією з цікавих
властивостей представлення у вигляді двійкового дерева є те, що процедура record()
завжди буде видавати цілісні інформаційні елементи, що утворюють дерево, у
відсортованому порядку. Це ілюструє запит
Goal: record(OneRecord, work4(work4(end, „Денега”, 211, „начальник”, 450, end),
„Маслов”, 101, „оператор”, 200, work4(end, „Петренко”, 101, „менеджер”, 300,end),)
Який забезпечує видачу наступних результатів:
OneRecord = work(„Денега”, 211, „начальник”, 450);
OneRecord = work(„Маслов”, 101, „оператор”, 200);
OneRecord = work(„Петренко”, 101, „менеджер”, 300);

5.7 Порівняння різних видів представлення бази даних

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

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

Ефективність роботи з БД у вигляді двійкових дерев багато в чому визначається
знаннями процедур їх створення і перетворення. Розглянемо ряд процедур, що
оперують із двійковими деревами, що описуються структурами виду
tree(Left, Root, Right),
де Left – ліве піддерево, кожен елемент якого має структуру, аналогічну tree(),
Root – корінь (будь-яка довільна, обумовлена користувачем, структура), Right – праве
піддерево, що складається з елементів структури tree().
Побудова бінарного дерева. Задача створення упорядкованого дерева при
додаванні деякого елемента Х до впорядкованого дерева може бути сформульована в
такий спосіб:
Гранична умова: Додавання Х до порожнього дереву дає tree(end, X, end).
Рекурсивні умови: При включенні Х в tree(Left, Root, Right) треба розглянути два
випадки, для того, щоб результуюче дерево було упорядкованим.
1. Якщо Х менше, ніж Root, то Х додається до лівого піддерева.
2. Якщо Х більше, ніж Root, то Х варто додати до правого піддерева.

45