22. Загальна характеристика Деревоподібної (ієрархічна) структура

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

Рис. 3.1- Ієрархічна структура даних

Як правило, при роботі з деревом виділяють яку-небудь конкретну верхівку (початок), визначають її як коріння дерева і розглядають особливо - в цю верхівку не заходить жодне ребро. В цьому випадку дерево стає орієнтованим. Орієнтація на кореневому дереві визначається або від коріння, або до коріння.

Кореневе дерево можна визначити наступним чином:

1) є єдиний особливий вузол , який називається корінням, в який не заходить жодне ребро;

2) в всі інші вузли заходить тільки одне ребро, а виходить довільна (0, 1, 2,..., п) кількість ребер;

3) не існує циклів.

В програмуванні використовується інше визначення дерева, яке дозволяє розглядати дерево як рекурсивну структуру.

Рекурсивне дерево визначається як кінцева множина Т, яка складається з одного або більш вузлів, таких, що:

1) існує один спеціально виділений вузол, який називається корінням дерева;

2) інші вузли розбиті на m>0 неперетинаючихся підмножини T1,T2, …, Tm, кожна з яких в свою чергу є деревом. T1,T2, …, Tm, називаються піддеревами.

23. Основні поняття:

Вузол — це сукупність атрибутів даних, що описують деякий об'єкт. На схемі ієрархічного дерева вузли представляються вершинами графа. Кожний вузол на більше низькому рівні зв'язаний тільки з одним вузлом, що перебуває на більше високому рівні. Ієрархічне дерево має тільки одну вершину (корінь дерева), не підлеглу ніякій іншій вершині й находящуюся на самому верхньому (першому) рівні. Залежні (підлеглі) вузли перебувають на другому, третьому й т.д. рівнях. Кількість дерев у базі даних визначається числом кореневих записів.

Атрибути - властивість, якісна або кількісна ознака, що характеризує просторовий об'єкт (але не пов'язаний з його місцевказанням)

Типи вузлів: залежні, незалежні.

Коріння – ланцюжок вершин, який веде від даної вершини до кореневої.

Листя - сукупність поточної вершини та всіх підпорядкованих їй вершин.

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

Не збалансоване – не однакова.

Бінарне – пошла она на хуй, нет такого во всём гугле..)) пиши кєпом, вдруг не прочитает..))

24. Основні вимоги до ієрархічних структур данних.

Ієрархічна БД складається з упорядкованого набору дерев; більш точно, з упорядкованого набору кількох екземплярів одного типу дерева.

Організація даних у СУБД ієрархічного типу визначається в термінах: елемент, агрегат, запис (група), групове відношення, база даних.

• Атрибут (елемент даних) - найменша одиниця структури даних. Звичайно кожному елементу при описі бази даних присвоюється унікальне ім'я. По цьому імені до нього звертаються при обробці. Елемент даних також часто називають полем.

• Запис - іменована сукупність атрибутів. Використання записів дозволяє за одне звертання до бази отримати деяку логічно зв'язану сукупність даних. Самі записи змінюються, додаються і видаляються. Тип запису визначається складом його атрибутів. Екземпляр запису - конкретний запис із конкретним значенням елементів

• Групове відношення - ієрархічне відношення між записами двох типів. Батьківський запис (власник групового відношення) називається вихідним записом, а дочірні записи (члени групового відношення) - підлеглими. Ієрархічна база даних може зберігати тільки такі деревоподібні структури.

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

Організація ієрархічної деревоподібної структури:

• усі типи зв'язків повинні бути функціональними (1:1, 1:M, M:1);

• дерево являє собою неорієнтований граф, що не містить циклів.

• тип дерева складається з одного "кореневого" типу запису й упорядкованого набору з нуля чи більше типів піддерев (кожне з який є деяким типом дерева).

• у дереві кожен вузол i-рівня зв'язаний тільки з одним батьківським вузлом (i-1)-рівня (будь-який син може мати не більш одного рідного батька, а будь-який батько - безліч синів);

• дуга дерева відповідає типу зв'язку "вихідний-породжений";

• доступ до кожного породженого вузла виконується безпосередньо через вихідний вузол;

• всі екземпляри даного типу нащадка з загальним екземпляром типу предка називаються близнюками.