8.6 Представлення бази даних у виді двійкового дерева

Можна ще більш удосконалити метод представлення даних у виді рекурсивної структури, якщо перетворити структуру work3() у структуру типу двійкове дерево. Це досягається шляхом введення в структуру запису БД ще одного додаткового аргументу, що вказує на попередній запис.

Зміст використання двійкового дерева полягає в тім, щоб зберігати базу даних у відсортованому виді. У розглянутому нижче прикладі база даних відсортована за атрибутом, що описує ім'я службовця і представляється бінарним деревом, що представлене на рис. 1.1.

Рисунок 8.1 – Структура двійкового дерева

Тепер у структурі інформаційного елемента буде шість аргументів:

work4(LeftTree, Name, Office, Post, Salary, RightTree)

Змінна LeftTree описує вітку дерева, що містить усі цілісні інформаційні елементи, що знаходяться (за алфавітом) перед поточним елементом. Змінна RightTree описує вітку дерева, що охоплює всі цілісні інформаційні елементи, розташовані відповідно до алфавіту, після даного елемента. Через те, що БД відсортована, цілісний інформаційний елемент, що містить відомості про Денегу, є самим верхнім вузлом дерева, а саму БД, представлену у виді двійкового дерева (рис.1.1), можна записати в такий спосіб:

work4(work4(end, Денега, 211, „начальник”, 450, end), „Маслов”, 101, „оператор”, 200, work4(end, „Петренко”, 101, „менеджер”, 300,end))

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

– запис належить дереву, якщо він знаходиться в лівому піддереву,

– запис належить дереву, якщо він є коренем цього дерева,

– запис належить дереву, якщо він знаходиться в правому піддереві.

Цю процедуру, використовуючи синтаксис Прологу, можна описати в такий спосіб:

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);

Завдання 8.4. Змініть попередню програму для роботи з БД, що представляється у вигляді двійкового дерева і дозволяє реалізувати запити до неї, описані в даному розділі.

Включіть вміст вихідної БД у виді двійкового дерева до складу програми і виконаєте до неї запити, аналогічні вище приведеному. Текст програми, запити і відповіді на них привести в звіті.