1. Нелінійна організація даних
1.1 Деревовидна організація даних
Нелінійна організація даних - це безліч записів, кожна з яких пов'язана з довільною кількістю попередніх і наступних записів. Найбільш використовуваними варіантами нелінійної організації даних є дерева і нелінійні списки.
Деревом називається безліч записів, розташованих за рівнями за такими правилами: на першому рівні розташована тільки одна запис (корінь дерева), до будь-якого запису i-го рівня веде адресу зв'язку тільки від одного запису (i - 1 ) - го рівня. Кількість рівнів в дереві називається рангом. Для виконання завдання скористаємося даними алгоритмом побудови упорядкованого бінарного дерева:
1. Перший запис масиву з ключем А 1 стає коренем дерева;
2. Значення ключа другого запису А 2 порівнюється з А 1, що знаходиться в корені дерева;
. Якщо А 2 < А 1, то другий запис розміщується на лівому від кореня гілки, в іншому випадку - на правій гілці;
. Далі на кожному кроці створюється впорядковане дерево з перших i записів;
5.Вибор місця i-й записи масиву в дереві проводиться таким чином. Ключ Аi порівнюється з кореневим значенням і виконується перехід по лівому адресою, якщо А1> Аi. Якщо А1 Аi, то по правому адресою. Ключ, записаний за цією адресою, порівнюється з Аi, і знову організовується перехід по лівому або правому адресою до знаходження вільного місця. Якщо необхідна адреса не заповнений, то він повинен адресувати запис з ключем Аi.
Завдання 1. Побудувати впорядковане бінарне дерево з наступними значеннями ключових ознак і підрівняти їх (докласти докладний протокол підрівнювання з усіма итерациями та описами їх): 62, 30, 70, 85, 35, 96, 26, 18, 47, 66, 42, 34, 71, 54, 93.
Побудуємо впорядковане бінарне дерево для записів з ключовими ознаками: 62, 30, 70, 85, 35, 96, 26, 18, 47, 66, 42, 34, 71, 54, 93 (рис. 2.1).
Впорядковане бінарне дерево побудовано таким чином:
1. Перший запис з ключем 62 стає коренем дерева;
2. Значення ключа другого запису 30 порівнюється з 62 (30 <62), запис поміщаємо на лівій від кореня гілки;
. Далі порівнюємо ключ третин записи 70 з Корев значенням 62 (70> 62), запис поміщаємо на правій від кореня гілки;
Рисунок 2.1 - Впорядковане бінарне дерево
4. Порівнюємо ключ 85 з Корев значенням 62 (85> 62), виконується перехід по правому адресою, далі порівнюємо значення 85 із значенням 70 (85> 70), запис поміщаємо на правій гілці;
5. Порівнюємо ключ 35 з Корев значенням 62 (35 <62), виконується перехід по лівому адресою, далі порівнюємо значення 35 із значенням 30 (35> 30), запис поміщаємо на правій гілці;
. Порівнюємо ключ 96 з Корев значенням 62 (96> 62), виконується перехід по правому адресою, далі порівнюємо значення 96 із значенням 70 (96> 70), виконується перехід по правому адресою, далі порівнюємо значення 96 із значенням 85 (96> ; 85), запис поміщаємо на правій гілці;
. Порівнюємо ключ 26 з Корев значенням ...
