Алгоритми і структури даних

 

 

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

Червоно-чорне дерево (red-black tree) – це двійкове дерево пошуку, вершини якого розділені на червоні (red) і чорні (black). Таким чином, кожна вер-шина зберігає один додатковий біт – її колір.

При цьому повинні виконуватися певні вимоги, які гарантують, що глибина будь-яких двох листків дерева відрізняється не більше, ніж у два рази, тому дере-во можна назвати збалансованим (balanced).

Кожна вершина червоно-чорного дерева має поля color (колір), key (ключ), left (лівий нащадок), right (правий нащадок) і p (предок). Якщо у вершини відсут-ній нащадок або предок, відповідне поле містить значення nil. Для зручності ми будемо вважати, що значення nil, які зберігаються в полях left і right, є посилан-нями на додаткові (фіктивні) листки дерева. При такому заповненні дерева кожна стара вершина, що містить ключ, має двох нащадків.

Двійкове дерево пошуку називається червоно-чорним деревом, якщо воно має такі властивості (будемо називати їх RB-властивостями, red-black properties):

1) кожна вершина або червона, або чорна;

2) кожен листок (nil) – чорний;

3) якщо вершина червона, обидва її нащадки – чорні;

4) всі шляхи, що йдуть вниз від кореня дерева до його листків, містять однакову кількість чорних вершин.

Операції Tree-Insert і Tree-Delete виконуються на червоно-чорному дере-ві за час але вони змінюють дерево, і результат може не відповідати RB-властивостям. Щоб відновити ці властивості, треба перефарбувати деякі вершини і змінити структуру дерева.

Детально процес повороту та модифікації червоно-чорного дерева опи-сано у лекційному курсі.

 

 

Розробити програму, яка читає з клавіатури:

5) числа , при цьому

6) послідовність ключів (цілих, дійсних чисел або рядків (до сим-волів) залежно від варіанта завдання);

7) послідовність ключів.

Програма зберігає першу послідовність до червоно-чорного дерева.

Кожного разу, коли до дерева додається новий елемент, потрібно вивес-ти статистику (згідно з варіантом завдання):

1. Мінімальний елемент та його колір.

2. Максимальний елемент та його колір.

Після побудови дерева для кожного елемента другої послідовності по-трібно вивести результати наступних операцій над деревом (згідно з варіантом завдання):

1. Чи є елемент у дереві та його колір?

2. та його колір.

3. та його колір.

Використовувати готові реалізації структур даних (наприклад, STL) забо-ронено, але можна використати реалізацію рядків (наприклад, std::string у C++).

 

 

Варіант 1: мінімальний елемент та його колір; чи є елемент у дереві та його колір?

Варіант 2: мінімальний елемент та його колір; та його ко-лір.

Варіант 3: мінімальний елемент та його колір; та його колір.

Варіант 4: максимальний елемент та його колір; чи є елемент у дереві та його колір.

Варіант 5: максимальний елемент та його колір; та його колір.

Варіант 6: максимальний елемент та його колір; та йо-го колір.

 

 

Мета роботи: познайомитися з алгоритмами сортування та бінарним пошуком.

 

 

Багато алгоритмів використовують сортування як проміжний крок. Є ба-гато різних алгоритмів сортування; в конкретній ситуації вибір алгоритму сор-тування залежить від довжини послідовності, яку необхідно відсортувати, та від того, якою мірою вона вже відсортована, а також від типу наявної пам’яті.

Сортування бульбашкою (bubble sort) складається з повторюваних проходів по сортованому масиву. За кожен прохід елементи послідовно порів-нюються попарно, і якщо порядок у парі неправильний, виконується обмін елементів. Проходи по масиву повторюються раз або доти, поки на чер-говому проході не з’ясується, що обміни більше не потрібні, що означає – ма-сив відсортований. При кожному проході алгоритму по внутрішньому циклу черговий найбільший елемент масиву ставиться на своє місце в кінці масиву поруч з попереднім найбільшим елементом, а найменший елемент переміща-ється на одну позицію до початку масиву («плине» до потрібної позиції, як бу-льбашка у воді, звідси і назва алгоритму).

Сортування включенням (insertion sort) зручне для сортування ко-ротких послідовностей. Саме в такий спосіб зазвичай сортують карти: трима-ючи в лівій руці вже впорядковані карти і взявши правою рукою чергову кар-ту, ми вставляємо її в потрібне місце, порівнюючи з наявними і йдучи справа наліво.

Швидке сортування основане на принципі «розділяй і володарюй». Сортування ділянки відбувається так:

1. Елементи масиву переставляються так, щоб будь-який з елементів був не більший будь-якого з елементів , де – деяке число в інтервалі. Цю операцію ми будемо називати поді-лом (partition).

2. Процедура сортування рекурсивно викликається для масивів і .

3. Після цього масив