КУРСОВА РОБОТА
з дисципліни «Теорія алгоритмів»
Тема:«АВЛ-дерево»
ЗМІСТ
КУРСОВА РОБОТА 1
ВСТУП 4
1 ТЕОРЕТИЧНА ЧАСТИНА 6
1.1Балансування та обертання АВЛ-дерева 7
1.2 Алгоритм додавання вершини 10
Безпосередньо при вставці присвоюється нульовий баланс. Процес включення вершини складається з трьох частин: 10
1.3 Алгоритм видалення вершини 12
1.4 Розстановка балансів при видаленні 12
1.5 Розстановка балансів при одинарному обороті 13
Таблиця 1.1 - Залежності фінальних балансів від напрямку повороту і вихідного балансу вузла Pivot. 13
1.6 Розстановка балансів при подвійному оборті 14
1.7 Оцінка ефективності 15
2 ПРАКТИЧНА ЧАСТИНА 16
Усі приведені нижче приклади компонентів програми дивитись у додатку А. 16
2.1 Структура Node та ініціалізація елементу цієї структури 16
2.2 Допоміжні елементи 17
2.3 Вставка нового вузла 19
2.4 Операція видалення вузла та допоміжні функції 21
2.5 Пошук вузла дерева. 23
2.5 Друк дерева. 24
2.6 Фінальна функція 25
ВИСНОВКИ 26
Результатом нашої праці стало АВЛ-дерево, яке має функції додавання, видалення та друку. АВЛ-дерево, як вже було зазначено, це збалансоване дерево, різниця висот гілок якого не повинна бути більше одиниці. Для збалансування дерева ми використовували мале ліве обертання, мале праве обертання, велике ліве та велике праве обертання. Але замість того, щоб писати код для чотирьох обертань, ми скоротили їх кількість до двох, так як велике обертання – це два маленьких обертання. 26
АВЛ-дерево є досить недавнім відкриттям двох радянських винахідників Георгієм Адельсоном-Вельським та Євгенієм Ландісом. Ці дерева виконують дуже важливу і розумну роботу: вони гарантують, що ми зможемо використовувати усі властивості бінарних дерев пошуку і їх ефективне середовище виконання. Дерева АВЛ неймовірно корисні для забезпечення того, що незалежно від того, що ми додаємо або видаляємо з дерева АВЛ, наші структури досить розумні і досить гнучкі, щоб врівноважити себе і впоратися з усім, що ми додаємо в них. 26
ПЕРЕЛІК ДЖЕРЕЛ ПОСИЛАННЯ 27
1.Vaidehi Joshi, The Little AVL Tree That Could, 2017 – [Електронний ресурс]. – Режим доступу: 27
https://medium.com/basecs/the-little-avl-tree-that-could-86a3cae410c7 27
Час останнього звертання: 20.12.20 27
Час останнього звертання: 20.12.20 27
3.AVL Tree – [Електронний ресурс]. – Режим доступу: 27
https://en.wikipedia.org/wiki/AVL_tree 27
Час останнього звертання: 20.12.20 27
4.АВЛ дерево – [Електронний ресурс]. – Режим доступу: 27
https://uk.wikipedia.org/wiki/%D0%90%D0%92%D0%9B-%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE#%D0%91%D0%B0%D0%BB%D0%B0%D0%BD%D1%81%D1%83%D0%B2%D0%B0%D0%BD%D0%BD%D1%8F 27
Час останнього звертання: 20.12.20 27
5.nickme, АВЛ деревья, 2012 – [Електронний ресурс]. – Режим доступу: 27
https://habr.com/post/150732/ 27
Час останнього звертання: 20.12.20 27
ДОДАТОК А 28
ВИХІДНИЙ КОД ПРОГРАМИ 28
ВСТУП
Як виявляється, історія за деревом AVL прихована прямо в його назві. Дерева AVL винайшли Георгій Адельсон-Вельський та Євгеній Ландіс (два радянські винахідники). Ці структури є досить недавніми творіннями; Адельсон-Вельський і Ландіс вперше представили ідею, що стояла за ними, в 1962 р. У роботі, написаній співавтором і опублікованій під назвою "Алгоритм організації інформації"[1].
Для того, щоб дати поняття АВЛ-дерева нам необхідно дати визначення двійкового дерева пошуку. Двійкове дерево пошуку - ієрархічна структура даних в якій кожен вузол має не більше ніж два нащадка, причому значення ключа будь-якого вузла лівого піддерева довільного вузла Х менше, ніж значення самого вузла Х, а значення будь-якого вузла правого піддерева вузла Х більше або дорівнює значенню ключа вузла Х [2]. Важливою характеристикою двійкового дерева пошуку, що безпосередньо впливає на швидкість пошуку даних є коефіцієнт збалансованості. Коефіцієнтом збалансованості називають деяку константу k, на яку можуть відрізнятися висоти лівого і правого піддерева будь-якого довільного вузла X. Таким чином АВЛ-дерево - це двійкове дерево пошуку, для якого визначено коефіцієнт збалансованості k = 1
Завдання даної курсової роботи - реалізувати основні операції для АВЛ-дерева: додавання, видалення, друк, пошук значення, балансування. Двійкові дерева пошуку неймовірно потужні через їх логарифмічний час виконання - це те, шо робить їх настільки швидкими та ефективними. Дерева двійкового пошуку в кращому випадку запускаються у час O (log n), що означає, що навіть коли дерево зростає, пошук за деревом для одного конкретного вузла все ще досить швидкий, тому що на кожному рівні ми вирізали половину дерева, коли ми шукаємо його. Це робить дерево логарифмічним.
Але логарифмічна природа двійкових дерев пошуку застосовується тільки в тому випадку, якщо вони збалансовані. Кожне дерево АВЛ дотримується правила: якщо піддеревини вузла мають висоту h1 і h2, тоді абсолютне значення різниці цих двох висот повинно бути менше або дорівнює (≤) 1. Іншими словами, різниця між висотами двох підрядів у дереві АВЛ повинна ніколи не перевищує 1-го рівня. АВЛ-дерева є надзвичайно корисними для забезпечення того, що, незалежно від того, що ми додаємо або вилучаємо з дерева AVL, наші структури є розумними та достатньо гнучкими, щоб відновити баланс і керувати тим, що ми додаємо.
1 ТЕОРЕТИЧНА ЧАСТИНА
Ідеально збалансованим називається дерево, у якого для кожної вершини виконується вимога: число вершин у лівому та правому піддеревах не відрізняється. Однак ідеальну збалансованість досить складно підтримувати.
У деяких випадках при додаванні/видаленні може знадобитися значне перебудування дерева, що не гарантує логарифмічної складності. Тому Г.М. Адельсон - Вельский і Е.М. Ландіс ввели менш строге визначення балансу і доказали, що при такому визначенні можна написати програми додавання/видалення, що мають логарифмічну складність і зберігають дерево збалансованим.
Дерево вважаєтся збалансованим по АВЛ (далі просто "збалансованим"), якщо для кожної вершини виконується вимога: висота лівого та правого піддерев відрізняється не більше, ніж на 1. Не будь-яке збалансоване дерево ідеально збалансоване, але кожне ідеально збалансоване дерево збалансоване[4].
Бінарні дерева пошуку призначені для швидкого доступу до даних. В ідеалі розумно збалансоване дерево має висоту порядку O (log2n). Однак, при деяких випадках обставин дерево може виявитися виродженим. Розглянемо модифікований клас дерев, що має всі переваги бінарних дерев пошуку. Вони називаються збалансованими або АВЛ - деревами. Під збалансуванням будемо розуміти те, що для кожного вузла дерева висоти обох його піддерев розрізняються не більше ніж на 1.
Нові методи вставки та видалення в класі АВЛ - дерева гарантують, що всі вузли залишаться збалансованими по висоті.
У процесі додавання або видалення вузлів в АВЛ-дереві можливе виникнення ситуації, коли різниця висот деяких вузлів виявляється рівними 2 або -2, тобто виникає розбалансування піддерева. Для виправлення ситуації застосовуються обертання навколо тих чи інших вузлів дерева.
Зрівняти звичайне бінарне дерево та АВЛ-дерево можна за допомогою наступних рисунків(рисунок 1.1, рисунок 1.2)
Рисунок 1.1–Бінарне дерево та АВЛ-дерево
Рисунок1.2 - Бінарне дерево та АВЛ-дерево
Існує 4 типи обертань[4]:
1. Мале ліве обертання (рисунок1.3)
Дане обертання використовується тоді, коли (висота b-піддерева - висота L) = 2 і висота С <= висота R.(L < a < C < b < R)
Рисунок 1.3 - Мале ліве обертання
2. Мале праве обертання (рисунок1.4)
Дане обертання використовується тоді, коли (висота b-піддерева — висота R) = 2 і висота С <= висота L. (L < b < C < a < R)
Рисунок 1.4 - Мале праве обертання
3. Велике ліве обертання (рисунок1.5)
Дане обертання використовується тоді, коли (висота b-піддерева - висота L) = 2 і висота C-піддерева > висота R.
Велике ліве обертання = Мале праве обертання + Мале ліве обертання
Рисунок1.5 - Велике ліве обертання.
4. Велике праве обертання (рисунок1.6)
Дане обертання використовується тоді, коли (висота b-піддерева — висота R) = 2 і висота C -піддерева> висота L.
Велике праве обертання = Мале ліве обертання + Мале праве обертання
Рисунок1.6 - Велике праве обертання.
1.2 Алгоритм додавання вершини
Безпосередньо при вставці присвоюється нульовий баланс. Процес включення вершини складається з трьох частин:
Проходу по шляху пошуку, поки не переконаємося, що ключа в дереві немає.
Включення нової вершини у дерево і визначення результуючих показників балансування.
«Відступи» назад по шляху пошуку і перевірки в кожній вершині показника збалансованості. Якщо необхідно — балансування.
Будемо брати як результат функції - зменшилася висота дерева чи ні. Припустимо, що процес з лівої гілки повертається до батька (рекурсія йде назад), тоді можливі три випадки: { hl — висота лівого піддерева, hr — висота правого піддерева } Включення вершини в ліве піддерево призведе до
hl < hr: вирівняється hl = hr. Нічого робити не потрібно.
hl = hr: тепер ліве піддерево буде більше на одиницю, але балансування поки не потрібно.
hl > hr: тепер hl — hr = 2, —потрібне балансування.
У третій ситуації потрібно визначити балансування лівого піддерева. Якщо ліве піддерево цієї вершини (Tree^.Left^.Left) вище правого (Tree^.Left^.Right), то потрібно велике праве обертання, інакше вистачить малого правого. Аналогічні (симетричні) міркування можна привести і для включення в праве піддерево[3].
1.3 Алгоритм видалення вершини
Для простоти опишемо рекурсивний алгоритм видалення. Якщо вершина — листок, то видалимо її і викличемо балансування всіх її предків в порядку від батька до кореня. Інакше знайдемо саму близьку за значенням вершину в піддереві найбільшої висоти (правому або лівому) і перемістимо її на місце видалення вершини, при цьому викликаючи процедуру її видалення[5].
1.4 Розстановка балансів при видаленні
Як вже було зазначено, якщо видаляється вершина — листок, то вона видаляється, і зворотний обхід дерева походить від батька видаленого листка. Якщо не лист, то знаходиться «заміна», і зворотний обхід дерева йде від батька «заміни». Безпосередньо після видалення елемента — «заміна» отримує баланс та видаляється вузла.
При зворотному обході: якщо при переході до батька прийшли зліва — баланс збільшується на 1, якщо ж прийшли праворуч — зменшується на 1.
Це робиться до тих пір, поки при зміні балансу він не стане рівним −1 або 1. Повороти відбуваються за тими ж правилами, що і при вставці.
1.5 Розстановка балансів при одинарному обороті
Позначимо:
«Current» — вузол, баланс якого дорівнює −2 або 2: тобто той, який потрібно повернути.
«Pivot» — вісь обертання. +2: Лівий син Current'а, −2: правий син Current'а.
Якщо поворот здійснюється при вставці елементу, то баланс Pivot'а дорівнює або 1, або −1. У такому випадку після повороту баланси обох встановлюються рівними 0[3].
При видаленні все інакше: баланс Pivot'а може стати рівним 0 (в цьому легко переконатися).
Наведемо зведену таблицю (таблиця 1.1) залежності фінальних балансів від напрямку повороту і вихідного балансу вузла Pivot:
Таблиця 1.1 - Залежності фінальних балансів від напрямку повороту і вихідного балансу вузла Pivot.
| Напрям повороту | Old Pivot.Balance | New Current.Balance | New Pivot.Balance |
| Лівий або Правий | −1 или +1 | 0 | 0 |
| Правий | 0 | −1 | +1 |
| Лівий | 0 | +1 | −1 |
1.6 Розстановка балансів при подвійному оборті
Pivot і Current — ті ж самі, але додається третій учасник повороту. Позначимо його за «Bottom»: це (при подвійному правому повороті) лівий син Pivot'а, а при подвійному лівому — правий син Pivot'а. При даному повороті — Bottom в результаті завжди набуває баланс 0, але від його вихідного балансу залежить розстановка балансів для Pivot і Current.
Наведемо зведену таблицю (таблиця 1.2) залежності фінальних балансів від напрямку повороту і вихідного балансу вузла Bottom:
Таблиця 1.2 - Залежності фінальних балансів від напрямку повороту і вихідного балансу вузла Bottom.
| Напрям | Old Bottom.Balance | New Current.Balance | New Pivot.Balance |
| Лівий або Правий | 0 | 0 | 0 |
| Правий | +1 | 0 | −1 |
| Правий | −1 | +1 | 0 |
| Лівий | +1 | −1 | 0 |
| Лівий | −1 | 0 | +1 |
1.7 Оцінка ефективності
Г. М. Адельсон-Вельський і Е. М. Ландіс довели теорему, згідно з якою висота АВЛ-дерева з N внутрішніми вершинами укладена між log2 (N +1) і 1.4404 * log2 (N +2) −0.328, тобто висота АВЛ -дерева ніколи не перевищить висоту ідеально збалансованого дерева більш, ніж на 45%. Для великих N має місце оцінка 1.04 * log2 (N). Таким чином, виконання основних операцій (вставка, пошук, видалення) вимагає порядку log 2 (N) порівнянь. Експериментально з'ясовано, що одна балансування припадає на кожні два включення і на кожні п'ять видалень. Практичне підтвердження дивитись у додатку В.
При балансуванні виконуються мале праве і велике праве обертання, що визначаються симетрично малому лівому і великим лівому обертанню. У кожному разі операція призводить до потрібного результату, а повна висота зменшується не більше ніж на 1 і не може збільшитися.
Все обертання, очевидно, вимагають O (1) операцій[4].
2 ПРАКТИЧНА ЧАСТИНА
Усі приведені нижче приклади компонентів програми дивитись у додатку А.
2.1 Структура Node та ініціалізація елементу цієї структури
Для реалізації дерева нам потрібна структура, яка визначає вузол дерева. Назвемо її, як це роблять зазвичай - Node. (рисунок 2.1)
Рисунок 2.1 – структура Node
Поля left і right вказуватимуть, відповідно, на ліву та праву «дитину». Поле key збергігає унікальний ключ цього вузла - його значення. Поле height вказує на положення вузла у дереві, його висоту.
Після цього, визначмо функції для ініціалізації екземпляру структуру Node, за наданими значения key, а також ініціалізуємо поля left, right, height значеннями NULL, NULL та 1 відповідно. (рисунок 2.2)
Рисунок 2.2 - ініціалізація екземпляру структури Node
2.2 Допоміжні елементи
Для подальшої роботи нам знадобляться певні функції, які ми зараз визначемо. int height(struct Node *N) – повертає значення поля height елемента Node. (рисунок 2.3)
Рисунок 2.3 – визначення висоти дерева
А також int max(int a, int b) яка повертає більше з двох значень типу int.(рисунок 2.4)
Рисунок 2.4 – визначення більшого елементу
Після цього визначемо функції struct Node *leftRotate(struct Node *x)(рисунок2.5) та struct Node *rightRotate(struct Node *y)(рисунок2.6), які повертають вказівник на під-дерево коренем якого є елемент struct Node *y.
Рисунок2.5 – лівий поворот
Рисунок2.5 – правий поворот
У подальшому нам знадобиться функція яка дозволить отримати значення балансовогу фактору дерева елементів Node.(рисунок 2.7)
Рисунок 2.7 – значення балансу
2.3 Вставка нового вузла
Тепер, визначимо функцію insert, яка вставляє елемент структури Node у існуюче AVL дерево АБО створює це дерево.(рисунок 2.7)
Рисунок 2.7 – вставка нового вузла
Усі попередні функції допомагають нам сконструювати AVL дерево елементів структури Node. Тепер, створимо функціонал для видалення елементу з дерева цих елементів.
2.4 Операція видалення вузла та допоміжні функції
Створимо функцію minValueNode – яка буде знаходити найменше значення у всьому AVL дереві. (рисунок 2.8)
Рисунок 2.8 – мінімальне значення у дереві
Отже, тепер, ми маємо усе необхідне аби створити функцію яка буде видаляти елемент з AVL дерева структури Node. Ця функція - deleteNode - видаляє елемент за наданим значенням key, приймає у якості аргументів посилання цілочисельне значення key та посилання на корінь AVL дерева. Повертає вона посилання на корінь суб-дерева яке було змінено. (рисунок 2.9)
Рисунок 2.9 – видалення вузла дерева
Рисунок 2.9 – видалення вузла дерева, аркуш 2
2.5 Пошук вузла дерева.
Для пошуку елемента реалізуємо функцію, яка приймає в якості параметрів корінь дерева і шуканий ключ. Для кожного вузла функція порівнює значення його ключа з шуканим ключем. Якщо ключі однакові, то функція повертає поточний вузол, в іншому випадку функція викликається рекурсивно для лівого або правого піддерева.( рисунок 2.10 )
Рисунок 2.10 – пошук вузла дерева
2.5 Друк дерева.
Останнє – створимо функцію яка буде друкувати дерево елемнтів Node за принципом preorder traversal(рисунок 2.11)
Рисунок 2.11 – функція друку дерева
2.6 Фінальна функція
Отже, ми маємо усе необхідне аби виконати наше завдання. Збираємо усі попередні функції у функції main() (рисунок 2.12). Приклад результату роботи програми дивитись у додатку Б.
Рисунок 2.12 – функція main()
ВИСНОВКИ
Результатом нашої праці стало АВЛ-дерево, яке має функції додавання, видалення та друку. АВЛ-дерево, як вже було зазначено, це збалансоване дерево, різниця висот гілок якого не повинна бути більше одиниці. Для збалансування дерева ми використовували мале ліве обертання, мале праве обертання, велике ліве та велике праве обертання. Але замість того, щоб писати код для чотирьох обертань, ми скоротили їх кількість до двох, так як велике обертання – це два маленьких обертання.
АВЛ-дерево є досить недавнім відкриттям двох радянських винахідників Георгієм Адельсоном-Вельським та Євгенієм Ландісом. Ці дерева виконують дуже важливу і розумну роботу: вони гарантують, що ми зможемо використовувати усі властивості бінарних дерев пошуку і їх ефективне середовище виконання. Дерева АВЛ неймовірно корисні для забезпечення того, що незалежно від того, що ми додаємо або видаляємо з дерева АВЛ, наші структури досить розумні і досить гнучкі, щоб врівноважити себе і впоратися з усім, що ми додаємо в них.
ПЕРЕЛІК ДЖЕРЕЛ ПОСИЛАННЯ
Vaidehi Joshi, The Little AVL Tree That Could, 2017 – [Електронний ресурс]. – Режим доступу:
https://medium.com/basecs/the-little-avl-tree-that-could-86a3cae410c7
Час останнього звертання: 20.12.20
Вирт Н., Алгоритмы и структуры данных. СПб.: Невский Диалект, 2008. 352 с. ISBN 978-5-7940-0065-8.
Час останнього звертання: 20.12.20
AVL Tree – [Електронний ресурс]. – Режим доступу:
https://en.wikipedia.org/wiki/AVL_tree
Час останнього звертання: 20.12.20
АВЛ дерево – [Електронний ресурс]. – Режим доступу:
https://uk.wikipedia.org/wiki/%D0%90%D0%92%D0%9B-%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE#%D0%91%D0%B0%D0%BB%D0%B0%D0%BD%D1%81%D1%83%D0%B2%D0%B0%D0%BD%D0%BD%D1%8F
Час останнього звертання: 20.12.20
nickme, АВЛ деревья, 2012 – [Електронний ресурс]. – Режим доступу:
https://habr.com/post/150732/
Час останнього звертання: 20.12.20
ДОДАТОК А
ВИХІДНИЙ КОД ПРОГРАМИ
#include
#include
#include
struct Node
{
int key;
struct Node *left;
struct Node *right;
int height;
};
int max(int a, int b);
int height(struct Node *N)
{
if (N == NULL)
return 0;
return N->height;
}
int max(int a, int b)
{
return (a > b)? a : b;
}
struct Node* newNode(int key)
{
struct Node* node = (struct Node*)
malloc(sizeof(struct Node));
node->key = key;
node->left = NULL;
node->right = NULL;
node->height = 1;
return(node);
}
struct Node *rightRotate(struct Node *y)
{
struct Node *x = y->left;
struct Node *T2 = x->right;
x->right = y;
y->left = T2;
y->height = max(height(y->left), height(y->right))+1;
x->height = max(height(x->left), height(x->right))+1;
return x;
}
struct Node *leftRotate(struct Node *x)
{
struct Node *y = x->right;
struct Node *T2 = y->left;
y->left = x;
x->right = T2;
x->height = max(height(x->left), height(x->right))+1;
y->height = max(height(y->left), height(y->right))+1;
return y;
}
int getBalance(struct Node *N)
{
if (N == NULL)
return 0;
return height(N->left) - height(N->right);
}
struct Node* insert(struct Node* node, int key)
{
if (node == NULL)
return(newNode(key));
if (key < node->key)
node->left = insert(node->left, key);
else if (key > node->key)
node->right = insert(node->right, key);
else
return node;
node->height = 1 + max(height(node->left),
height(node->right));
int balance = getBalance(node);
if (balance > 1 && key < node->left->key)
return rightRotate(node);
if (balance < -1 && key > node->right->key)
return leftRotate(node);
if (balance > 1 && key > node->left->key)
{
node->left = leftRotate(node->left);
return rightRotate(node);
}
if (balance < -1 && key < node->right->key)
{
node->right = rightRotate(node->right);
return leftRotate(node);
}
return node;
}
struct Node * minValueNode(struct Node* node)
{
struct Node* current = node;
while (current->left != NULL)
current = current->left;
return current;
}
struct Node* search(struct Node* root, int key)
{
if (root == NULL || root->key == key)
return root;
if (root->key < key)
return search(root->right, key);
return search(root->left, key);
}
struct Node* deleteNode(struct Node* root, int key)
{
if (root == NULL)
return root;
if ( key < root->key )
root->left = deleteNode(root->left, key);
else if( key > root->key )
root->right = deleteNode(root->right, key);
else
{
if( (root->left == NULL) || (root->right == NULL) )
{
struct Node *temp = root->left ? root->left :
root->right;
if (temp == NULL)
{
temp = root;
root = NULL;
}
else
*root = *temp;
free(temp);
}
else
{
struct Node* temp = minValueNode(root->right);
root->key = temp->key;
root->right = deleteNode(root->right, temp->key);
}
}
if (root == NULL)
return root;
root->height = 1 + max(height(root->left),
height(root->right));
int balance = getBalance(root);
if (balance > 1 && getBalance(root->left) >= 0)
return rightRotate(root);
if (balance > 1 && getBalance(root->left) < 0)
{
root->left = leftRotate(root->left);
return rightRotate(root);
}
if (balance < -1 && getBalance(root->right) <= 0)
return leftRotate(root);
if (balance < -1 && getBalance(root->right) > 0)
{
root->right = rightRotate(root->right);
return leftRotate(root);
}
return root;
}
void preOrder(struct Node *root)
{
if(root != NULL)
{
printf("%d ", root->key);
preOrder(root->left);
preOrder(root->right);
}
}
int main() {
struct Node *root = NULL;
struct timespec start, end;
int n = 2000;
int b = 50000;
clock_gettime(CLOCK_REALTIME, &start);
printf("Insertion 2000\n");
for (int i =0;i
root = insert(root, i);
}
clock_gettime(CLOCK_REALTIME, &end);
printf("\nExecution time: %lf\n", (end.tv_sec - start.tv_sec)+((end.tv_nsec - start.tv_nsec)/1000000000.0));
for (int i =n;i
root = insert(root, i);
}
clock_gettime(CLOCK_REALTIME, &start);
printf("\nPreorder traversal of the constructed AVL "
"tree is \n");
preOrder(root);
clock_gettime(CLOCK_REALTIME, &end);
printf("\nExecution time: %lf\n", (end.tv_sec - start.tv_sec)+((end.tv_nsec - start.tv_nsec)/1000000000.0));
printf("\ndeletion 2000\n");
clock_gettime(CLOCK_REALTIME, &start);
for (int i =1;i
root = deleteNode(root, i);
}
clock_gettime(CLOCK_REALTIME, &end);
printf("\nExecution time: %lf\n", (end.tv_sec - start.tv_sec)+((end.tv_nsec - start.tv_nsec)/1000000000.0));
clock_gettime(CLOCK_REALTIME, &start);
printf("\nSearch 2000\n");
for (int i =n;i<4000;i++){
root = search(root, i);
}
clock_gettime(CLOCK_REALTIME, &end);
printf("\nExecution time: %lf\n", (end.tv_sec - start.tv_sec)+((end.tv_nsec - start.tv_nsec)/1000000000.0));
return 0;
}
ДОДАТОК Б
РЕЗУЛЬТАТИ РОБОТИ ПРОГРАМИ (РИСУНОК Б.1, Б.2)
Рисунок Б.1 - Результати тестування 1
Рисунок Б.2 - Результати тестування 1.1
ДОДАТОК В
ПОРІВНЯННЯ ЧАСУ РОБОТИ ПРОГРАМИ (Таблиця В.1)
| Кількість елементів, з якими була виконана операція | вставка | видалення | пошук |
| 2000 | 998 | 1000 | 995 |
| 5000 | 1595 | 1520 | 1498 |
| 50000 | 17169 | 16997 | 17034 |
| 75000 | 24934 | 24872 | 24951 |
| 90000 | 30943 | 29946 | 30857 |
Таблиця В.1 – порівняння часу (в наносекундах) роботи програми з різною кількістю даних
ПОРІВНЯЛЬНІ ГРАФІКИ ЗА ДАНИМИ ТАБЛИЦІ
(Графік В.1, В.2, В.3, В.4)
Графік В.1 – порівняльний графік за даними таблиці
Графік В.2 – Час виконання вставки
Графік В.2 – Час виконання видалення
Графік В.2 – Час виконання пошуку