Дерево пошуку – Scapegoat tree

Міністерство освіти і науки України

Харківський національний університет імені В. Н. Каразіна

Факультет комп’ютерних наук

КУРСОВА РОБОТА

з дисципліни: «Теорія алгоритмів»

Тема: «Дерево пошуку – Scapegoat tree»

Виконав студент 2 курсу, групи КІ-21

Васильченко Дмитро Олександрович

Перевірили:

доц. Щебенюк В.С.

Маций О.Б.

Харків – 2022

ЗМІСТ

ВСТУП        4

РОЗДІЛ 1 АЛГОРИТМ TANGO TREE        5

1.1        Опис алгоритму        5

1.2        Степінь балансування дерева        5

1.3        Переваги та недоліки алгоритму        6

1.4        Властивості алгоритму        7

РОЗДІЛ 2 СТРУКТУРА АЛГОРИТМУ        8

РОЗДІЛ 3 ОПЕРАЦІЇ        10

3.1        Пошук        10

3.2        Вставка        10

3.3        Перебалансування        11

3.4        Видалення вершини        12

РОЗДІЛ 4 РЕЗУЛЬТАТИ РОБОТИ АЛГОРИТМУ        13

ВИСНОВОКИ        16

ВСТУП

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

Структуру даних, яка називається Scapegoat-деревом. «Scapegoat tree», перекладається як «цап-відбувайло», що робить дослівний переклад назви якимось дивним, але максимально описує цей алгоритм.

Scapegoat tree є самобалансуючим варіантом бінарного дерева пошуку. На відміну від інших варіантів, таких як red-black tree та AVL tree, scapegoat tree є необтяженою структурою даних. Тобто йому не потрібне додаткове сховище для кожного вузла в дереві. Низькі накладні витрати та проста реалізація роблять алгоритм Scapegoat tree дуже привабливою структурою даних. Алгоритм scapegoat tree слід використовувати в програмах, де домінують операції вставки та пошуку, оскільки саме там він є найбільш ефективним.

РОЗДІЛ 1 АЛГОРИТМ TANGO TREE

1. Опис алгоритму

Алгоритм scapegoat tree є реалізацією бінарного дерева, що самобалансується. Ця структура базується на загальноприйнятій думці про те, що коли щось йде не так, люди перше, що роблять, це шукають когось, кого можна звинуватити, так званого «цапа-відбувайла». Як тільки провину буде встановлено, ми можемо залишити цапа-відбувайла, щоб вирішити проблему.

1. Степінь балансування дерева

Дерев пошуку є дуже багато різних видів, і в основі всіх їх лежить та сама ідея: “А добре б при пошуку елемента перебирати не весь набір даних поспіль, а тільки якусь частину, бажано розміру” порядку log(N).

Для цього кожна вершина зберігає посилання на своїх дітей і якийсь критерій, за яким при пошуку точно зрозуміло, яку з дочірніх вершин треба перейти. За логарифмічний час це все працюватиме тоді, коли дерево є збалансованим (або прагне цього) – тобто, коли «висота» кожного з піддерев кожної вершини приблизно однакова. А ось способи балансування дерева вже у кожного типу дерев свої: у червоно-чорних деревах у вершинах зберігаються маркери «кольору», що підказують коли і як потрібно перебалансувати дерево, в AVL-деревах у вершинах зберігається різниця висот дітей, Splay-дерева заради балансування змушені змінювати дерево під час пошукових операцій, тощо.