25. Операції над деревами.

Дерево (англ. tree) — в інформатиці та програмуванні одна з найпоширеніших структур даних. Формально дерево визначається як скінченна множина Т з однієї або більше вершин (вузлів, nodes), яке задовольняє наступним вимогам:

1. існує один відокремлений вузол — корінь (root) дерева

2. інші вузли (за виключенням кореня) розподілені серед m ≥ 0 непересічних множин T₁…T_m і кожна з цих множин в свою чергу є деревом. Дерева T₁…T_m мають назву піддерев (subtrees) даного кореня.

Операції над деревами

Важливими операціями на деревах є:

• обхід вершин в різному порядку

• перенумерація вершин

• пошук елемента

• додавання елемента у визначене місце в дереві

• видалення елемента

• видалення цілого фрагмента дерева

• додавання цілого фрагмента дерева

• трансформації (повороти) фрагментів дерева

• знаходження кореня для будь-якої вершини

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

26.Типові оператори маніпулювання деревоподібними структурами.

Знайти зазначене дерево БД (наприклад, лікарню ©40); Перейти від одного дерева до іншого; Перейти від одного запису до іншого усередині дерева (наприклад, від палати - до першого пацієнта); Перейти від одного запису до іншої в порядку обходу ієрархії; Уставити новий запис у зазначену позицію; Видалити поточний запис.

Прикладами типових операторів маніпулювання ієрархічно організованими даними можуть бути наступні:

• Знайти зазначене дерево БД (наприклад, відділ 310);

• Перейти від одного дерева до іншого;

• Перейти від одного запису до іншго усередині дерева (наприклад, від відділу - до першого співробітника);

• Перейти від одного запису до іншої в порядку обходу ієрархії;

• Уставити новий запис у зазначену позицію;

• Видалити поточний запис.

27. Переваги та недоліки ієрархічної моделі даних.

ІМ (ієрархічна модель) : забезпечує незалежність за даними, але не забезпечує структурну незалежність.

Переваги:

1. забезпечує сумісне використання даних;

2. концептуальна простота забезпечується відношенням предок-нащпдок;

3. цілісність БД забезпечується відношенням предок-нащпдок;

4. ефективно працює з постійними зв'язками 1:М.

Недоліки:

1. навігаційна система ускладнює проектування, впровадження, розробку додатків, застосування і керування;

2. обмеження у реалізації (відсутність зв'язків М:N чи зв'язків з кількома предками);

3. відсутність у СУБД мови визначення даних чи мови маніпулювання даними;

4. відсутність стандартизації

28. Мови управління ієрархічноорганізованими данними.

Мова доступу до даних, яку підтримує IMS, дозволяє звертатися до елементів прямо, знаючи назву і, можливо, додаткову умову. Наприклад, можна роздрукувати назву всіх збірників, відповідальним редактором яких є Іванов:

Get Unique Збірник Where Відповідальний_редактор = "Іванов"

/* одержали перший збірник */

While true do

Print Збірник.Назва

Get next Збірник Where Відповідальний_редактор = "Іванов"

End while

Вибравши один зі збірників у попередньому прикладі, можна спуститися "униз" по ієрархії (оператор Get next Within Parent дозволяє перебрати всі элементы-потомки, що належать обраному елементу) і, наприклад, переглянути одну з статей чи кілька статей з обраного збірника

Get Unique Збірник Where Відповідальний_редактор = "Іванов"

/* одержали перший збірник */

While true do

Print "Збірник", Збірник.Назва

Get next Within Parent Статтья

While true do

Print Статтья.Назва

Get next Within Parent Стаття

End while

Get next Збірник Where Відповідальний_редактор = "Іванов"

End while