Деревовидні структури
Деревовидні структури — останній тип структур, які ми розглянемо.
Даний тип має схему організації типової компанії (рис. 9.10.), де на вершині знаходиться президент, від якого лінії йдуть до віце-президентів, за якими йдуть регіональні менеджери тощо. На цю структуру накладемо додаткове обмеження, яке полягає в тому, що один працівник не може знаходитися у підпорядкуванні двох керівників.
Кожен елемент дерева називається вузлом або вершиною. Найвища точка має назву кореневої вершини.
Вершини на протилежній стороні дерева мають назву кінцівок або листків
Вершина разом з її підструктурами називається піддеревом
Такий аналіз дозволяє посилатися на предків та нащадків даної вершини
Безпосередні предки даної вершини називаються материнськими вершинами
Безпосередні нащадки — дочірні вершини
Вершини, які мають спільну материнську вершину називають близнюками
Найдовша кількість вузлів від кореневої вершини до листа називається глибиною дерева
Пакет реалізації бінарних дерев
Бінарних деревах, тобто таких, які мають не більше двох дочірніх вершинТакі дерева зберігаються у пам’яті з використанням зв’язаних структур, аналогічних до зв’язаних списків. Замість двох компонентів бінарне дерево складається з трьох компонентів: значення даних, вказівника на першу дочірню вершину, вказівника на другу дочірню вершину. Перша дочірня вершина називається лівою, а друга — правою. Таким чином кожна вершина є коротким неперервним блоком пам’яті. Для зберігання дерева в пам’яті слід знайти доступні блоки комірок, яких достатньо для збереження окремих вершин, і зв’язати ці вершини відповідно до структури дерева. Тобто кожен вказівник треба встановити на ліву або праву дочірню вершину даної вершини, або присвоїти значення NIL. Відповідно у листків вказівники на обидві дочірні вершини дорівнюють NIL. Також слід звернути увагу на вказівник кореневої вершини — окрему комірку пам’яті, яка буде описувати дерево загалом.
Така структура забезпечує зручний метод пошуку будь-якої вершини дерева:її материнську вершину, або вершини, які мають спільну материнську вершину з даною. Місцезнаходження материнської вершини для даної вершини можна знайти,розділивши позицію даної вершини на 2 та відкинувши остачу.
Тема 10. Структури баз даних
Основні поняття бази даних
Категорії „Дані“ та „Модель даних“ є однією з базових концепцій Баз даних
Дані — є набором конкретних значень, параметрів, які визначають об’єкт, умову, ситуацію, або ж інші фактори
Дані не мають визначеної структури, вони набувають інформаційного значення лише коли користувач визначає певну структуру
Модель даних — певна абстракція, яка використовується щодо конкретних даних дозволяючи користувачам та розробникам інтерпретувати її як інформацію
Іншими словами, така інформація містить не лише дані, але й зв’язок між ними
В загальному випадку Технологія баз даних є синтезом структур даних та файлів
Щоб підкреслити відмінності між файловою системою та системою баз даних використовується термін „плоский файл“
Такий файл може розглядатися як одновимірна система зберігання інформації
База даних (БД) – набір даних, який є багатовимірним з точки зору наявності внутрішніх зв’язків між окремими елементами, що дозволяє отримувати доступ до інформації виходячи з різних точок
Історично БД розвивалися як засоби інтеграції систем зберігання даних
Причиною появи плоских файлів стала потреба обробки платіжних документів
Потреба в інтерактивній обробці даних призвела до появи архітектури з використанням індексованих файлів
Хоча кожна з цих архітектур поодинці є прогресивною, відсутність інтегрованих систем баз даних призводить до обмеженості і неефективності використання ресурсів
В результаті, ці системи використовувалися кожним підрозділом окремо, що призводило до збільшення документообігу
Як наслідок, виникла потреба у створенні інтегрованих БД.
У випадку використання інтегрованої БД, для її управління призначається адміністратор БД
Адміністратор приймає всі рішення, які пов’язані з організацією БД та доступом до неї
Для надання прав використовуються схеми та підсхеми
Схема — повний опис структури БД, яке використовується ПЗ для обслуговування БД загалом
Підсхема — опис частини БД, який використовується відповідно до потреб користувача