9.1 Мета роботи

Вивчення методів реалізації двійникових дерев та графів у середовищі мови С++. Отримання практичних навичок використання двійникових дерев та графів при вирішенні практичних завдань.

9.2 Організація самостійної роботи студентів

Під час підготовки до виконання лабораторної роботи необхідно вивчити індивідуальне завдання (п. 9.3), виконати розробку алгоритму вирішення задачі та підготовити текст програми щодо реалізації розробленого алгоритму, підготовити відповідні розділи звіту та вивчити відповідний теоретичний матеріал, який викладено у лекції: „Дерева та графи. Реалізація множини на базі дерев” та відповідного матеріалу у наступних підручниках і навчальних посібниках [1, 4, 5, 7, 8].

Граф – це фігура, що складається з вершин та ребер, які з'єднують вершини. Ребра можуть мати напрямок, тобто зображуватися стрілочками; такі графи називаються орієнтованими. Дерево – це зв'язаний граф без циклів. Крім того, у дереві виділена одна вершина, що називається коренем дерева. Інші вершини впорядковуються по довжині шляху від кореня дерева (рисунок 9.1).

Рисунок 9.1	Рисунок 9.2

Зафіксуємо деяку вершину X. Вершини, які з'єднані з X ребрами та розташовані далі від кореня дерева, називаються дітьми або синами вершини X. Сини впорядковані зліва-направо. Вершини, у яких немає синів, називаються термінальними. Дерево зображують переверненим, коренем догори.

Дерева в програмуванні використовуються значно частіше, ніж графи. Так, на побудові дерев засновано багато алгоритмів сортування та пошуку. Компілятори в процесі переведення програми з мови високого рівня на машинну мову представляють фрагменти програми у вигляді дерев, які називаються синтаксичними. Дерева застосовувати всюди, де є які-небудь ієрархічні структури, тобто структури, які можуть вкладатися одне а одне. Прикладом може служити зміст книги (рисунок 9.2).Файлову систему комп'ютера також можна представити у вигляді дерева. Вершинам відповідають каталоги (їх також називають директоріями або папками) та файли. З вершини-каталогу виходять ребра до вершин, що відповідають всім каталогам та файлам, які знаходяться в даному каталозі. Файли представляються термінальними вершинами дерева. Кореню дерева відповідає кореневий каталог диска.

Реалізації з посиланнями, ідеально підходять для реалізації дерев. Вершина дерева представляється у вигляді об'єкта, що містить посилання на батьківську вершину та на всіх синів, а також деяку додаткову інформацію, що залежить від конкретної задачі. Об'єкт, що представляє вершину дерева, займає область фіксованого розміру, яка розміщається в динамічній пам'яті. Кількість синів може бути обмеженою. Так, дуже часто розглядаються бінарні дерева, у яких кількість синів у довільної вершини не перевищує двох. Якщо один або декілька синів у вершини відсутні, то відповідні посилання містять нульові значення. Таким чином, у термінальних вершин всі посилання на синів нульові.

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

Нижче наведений ще один рекурсивний алгоритм, що визначає висоту дерева. Висотою дерева називається максимальна з довжин усіляких шляхів від кореня дерева до термінальних вершин. Під довжиною шляху розуміється число вершин, що входять у нього, включаючи першу й останню вершини. Так, дерево, що складається з однієї кореневої вершини, має висоту 1, дерево, наведене на рисунку 9.1 – висоту 4.

Алгоритм висота_дерева(вхід: вершина V)

| Дано: V - посилання на корінь піддерева

| Треба: Підрахувати висоту піддерева

початок

| цілий h, m, s;

| h := 1;

| якщо у вершини V є сини

| | те //Шукаємо піддерево максимальної висоти

| | m := 0;

| | цикл для кожного сина X вершини V виконати

| | | s := висота_дерева(X); //Рекурсія!

| | | якщо s > m

| | | | те m := s;

| | | кінець якщо

| | кінець циклу

| | h := h + m;

| кінець якщо

| відповідь := h;

кінець алгоритму

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

1) при додаванні та вилучені елементів у середині масиву доводиться переписувати елементи наприкінці масиву на нове місце, щоб звільнити місце для елемента, що додається, або закрити дірку, що утворилася, при вилученні елемента;

2) пошук виконується гарантовано швидко, але все-таки не миттєво.

Від першого із цих недоліків можна позбутися, застосовуючи замість безперервної реалізації на базі масиву посилальну реалізацію, при якій елементи множини знаходяться у вершинах бінарного дерева. Елементи у вершинах упорядковані таким чином, що, якщо зафіксувати деяку вершину V і розглянути два піддерева, що відповідають лівому та правому синам вершини, то всі елементи у вершинах лівого піддерева повинні бути менше, ніж елемент у вершині V, а всі елементи у вершинах правого піддерева повинні бути більше його (рисунок 9.3).

Рисунок 9.3	Рисунок 9.4

Для такого дерева можна застосовувати алгоритм бінарного пошуку. Максимальне число порівнянь при пошуку в такому дереві рівняється його висоті (тобто максимальній довжині шляху від кореня до термінальної вершини). Щоб пошук виконувався швидко, дерево повинне бути збалансованим, тобто всі його шляхи повинні мати майже однакову довжину.

Точне визначення збалансованості наступне: будемо вважати, що в кожної вершини, включаючи термінальні, рівно два сини, при необхідності додаючи зовнішні, або нульові, вершини. Наприклад, у термінальної вершини обоє сина нульові. (Це в точності відповідає представленню дерева в мові Сі, де кожна вершина зберігає два покажчики на синів; якщо сина нема, то відповідний покажчик нульової.) Звичайні вершини дерева називаються власними. Розглянемо шлях від кореня дерева до зовнішнього (нульовий) вершині. Довжиною шляху вважається кількість власних вершин у ньому. Дерево називається збалансованим, якщо довжини всіх можливих шляхів від кореня дерева до зовнішніх вершин розрізняються не більше ніж на одиницю. Іноді в літературі такі дерева називають майже збалансованими, розуміючи під збалансованістю строгу рівність довжин всіх шляхів від кореня до зовнішніх вузлів; ми, однак, будемо дотримуватися нестрогого визначення. Приклад збалансованого дерева представлений на рисунку 9.4.

Висота збалансованого дерева h логарифмічно залежить від числа вершин n: h <= log₂n + 1.

Оскільки максимальне число порівнянь при пошуку елемента в упорядкованому бінарному дереві дорівнюється висоті дерева, пошук у збалансованому дереві здійснюється дуже швидко, за час, що логарифмічно залежить від числа елементів множини. (Можна довести, що це є теоретичною оцінкою знизу: ніякий алгоритм не може в загальному випадку знаходити елемент швидше, ніж за log₂n операцій.)

Для ефективної реалізації множини на базі дерева процедури додавання й вилучення елементів повинні зберігати властивість збалансованості (або майже збалансованості). Розглянемо дві найбільш популярні схеми реалізації збалансованих дерев.

AVL-дерева (названі на честь їхніх двох винахідників Г.М. Адельсона-Вельського та Е.М. Ландиса) зберігають додатково в кожній вершині різницю між висотами лівого та правого піддеревьев. У збалансованому дереві для будь-якої вершини AVL-дерева різниця висот її лівого та правого піддеревьев по абсолютному значенню не повинна бути більше одиниці. При цьому довжини шляхів від кореня до зовнішніх вершин можуть розрізнятися більше, ніж на одиницю. Для AVL-дерев їхня висота оцінюється зверху логарифмічно залежно від числа вершин: h <= C log₂ n, де константа C = 1.5.

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

1. Обертання вершини x піддерева вліво (рисунок 9.5). Тут вершина x піддерева, що є його коренем, опускається донизу та вліво. Колишній правий син d вершини x стає новим коренем піддерева, а x стає лівим сином d. (Вершини x та d, начальник та підлеглий, як би міняються ролями: колишній начальник стає підлеглим.) Піддерево c, що було лівим сином вершини d, переходить у підпорядкування від вершини d до вершини x і стає її правим сином. При цьому що впорядкованість вершин зберігається: a < b < c< d < e. Таким чином, для виконання перетворення треба лише замінити фіксовану кількість покажчиків у вершинах x, d, c та, можливо, у батьківській для x вершині;

Рисунок 9.5

2. Обертання вершини x піддерева вправо (рисунок 9.6). Тут вершина x опускається донизу і вправо, її колишній лівий син b стає новим коренем піддерева, а x – його правим сином. Піддерево c переходить у підпорядкування від b до x.

Рисунок 9.6

Операції обертання носять локальний характер і дозволяють при необхідності виправити баланс піддерева з коренем x. Наприклад, для відновлення балансу дерева, показаного на рисунку 9.7, досить виконати одне обертання вершини b уліво.

Рисунок 9.7

У випадку AVL-дерев операції обертання повторюються в циклі при відновленні балансу після додавання або вилучення елемента, число обертань не перевищує С× h, де: h — висота дерева, C — константа. Таким чином, як пошук елемента, так і його додавання або вилучення виконується за логарифмічний час: t <= C · log₂n.

Зараз більш популярна інша схема: червоно-чорні дерева, або RB-дерева, від англ. Red-Black Trees (рисунок 9.8). Червоно-чорні дерева були уведені Р. Байером в 1972 р. У стандартній бібліотеці класів мови C++ виконавці множина та навантажена множина — класи set та map — реалізовані саме як червоно-чорні дерева.

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

1. Кожна зовнішня (або нульова) вершина вважається чорною;

2. Коренева вершина дерева чорна;

3. У червоної вершини діти чорні;

4. Усякий шлях від кореня дерева до довільної зовнішньої вершини має ту саму кількість чорних вершин.

Останній пункт визначення означає збалансованість дерева по чорних вершинах.

Рисунок 9.8

З пункту 3) визначення випливає, що в довільному шляху від кореня до термінальної вершини не може бути двох червоних вершин підряд. Це означає, що, оскільки число чорних вершин у будь-якому шляху однаково, довжини різних шляхів до термінальних вершин відрізняються не більш ніж удвічі. Це властивість близько по своїй суті до збалансованості.

Для червоно-чорного дерева справедлива наступна оцінка зверху на висоту дерева залежно від числа вершин: h <= 2 log₂ (n+1). Це означає, що пошук у червоно-чорному дереві виконується за логарифмічний час.

Нова вершина додається в червоно-чорне дерево як термінальна після процедури пошуку (цим RB-дерево нічим не відрізняється від інших упорядкованих дерев). Нова вершина фарбується в червоний колір. При цьому пункт 3) у визначенні червоно-чорного дерева може порушитися. Тому після додавання, а також вилучення вершини виконується процедура відновлення структури червоно-чорного дерева, що грає ту ж роль, що й відновлення балансу AVL-дерева. Перевага червоно-чорних дерев полягає в тому, що процедура відновлення більше проста. У багатьох випадках вона обмежується перефарбуванням вершин. У ній також можуть виконуватися операції обертання вершини вліво та вправо, але число обертань може бути не більше двох при додаванні елемента та не більше чотирьох при вилученні. Усього число операцій при відновленні структури RB-дерева оцінюється зверху через висоту дерева: число операцій <= K · h, де h – висота дерева, K – константа. Оскільки для висоти RB-дерева справедлива наведена вище логарифмічна оцінка від числа вершин n, одержуємо наступну оцінку: число операцій <= C log₂ n, де C - константа. Таким чином, додавання та вилучення елементів виконується у випадку червоно-чорних дерев за логарифмічний час залежно від числа вершин дерева.