что-то. ТА_42 Дерева пошуку. Розділ атд засновані на множинах. Дерева пошуку
 Скачать 1.6 Mb.
|
|
Розділ 4. АТД засновані на множинах. Дерева пошуку У цьому випадку для уявлення множини краще використати структури даних, які дозволяють ефективніше реалізувати загальний набір операторів, що виконуються над множинами. Проте ці структури значно складніші і найчастіше застосовуються тільки для великих множин. Всі вони засновані на різного роду деревах, таких як
с. 146-152 [1] Для знаходження за таким алгоритмом значення ключа серед n-елементної множини буде переглянуто O(log п)елементів. До функції передається ключове значення і покажчик на корінь дерева, а повертає функція покажчик на вузол, значення якого дорівнює шуканому. Як ознаку успішності пошуку використано логічну змінну found. Пошук починається з кореня дерева і триває доти, доки шукане значення не буде знайдене або доки всі вузли дерева не будуть перевірені. Дерева змінної структури, тобто такі, кількість елементів яких під час роботи певної програми може збільшуватися або зменшуватися, можна використовувати, зокрема, при створенні частотного словника. Задача створення частотного словника формулюється так: потрібно визначити, скільки разів зустрічається кожне слово в заданій послідовності слів. Послідовність слів можна зобразити у вигляді дерева бінарного пошуку. В інформаційних полях вузла такого дерева зберігатиметься слово і кількість його повторень. У разі виявлення в тексті чергового слова дерево переглядають, починаючи з кореневого вузла. Якщо слово в дереві знайдене, то лічильник його повторень збільшується. Але якщо слово в дереві не знайдене, воно включається в дерево із значенням лічильника, що дорівнює 1. Дану задачу називають іще пошуком із включенням. Включення вузла в дерево має здійснюватися так, щоб не порушувалася властивість упорядкованості ключів. Це правило буде дотримане, якщо застосувати розглянутий раніше алгоритм знаходження ключового значення у бінарному дереві пошуку, а включення нового елемента здійснювати тоді, коли пошук завершився безуспішно. Можливі три випадки видалення вузла бінарного дерева пошуку :
В кращому разі дерево може бути повністю збалансованим і містити приблизно logN вузлів між коренем і кожним із зовнішніх вузлів, але у гіршому разі в кожний з шляхів пошуку може містити N вузлів. Зокрема, довжина шляху і висота бінарних дерев безпосередньо пов'язані з витратами на пошук в BST-деревах. Висота визначає вартість пошуку у гіршому разі, довжина внутрішнього шляху безпосередньо пов'язана з вартістю влучень при пошуку, а довжина зовнішнього шляху безпосередньо пов'язана з вартістю промахів при пошуку. Найгірші випадки дерев пошуку Найгірші випадки дерев пошуку Хороший випадок дерева пошуку Хороший випадок дерева пошуку Найкращий випадок дерева пошуку Лема 2. Для виконання вставок і виявлення промахів при пошуку в дереві бінарного пошуку, утвореному N довільними ключами, в середньому потрібно біля 2 logN÷1.39 logN порівнянь. Леми 1 і 2 визначають продуктивність для середнього випадку за умови, що порядок ключів довільний. Якщо це не так, продуктивність алгоритму має тенденцію до зниження. Лема 3. У гіршому разі для пошуку в дереві бінарного пошуку з N ключами може бути потрібним N порівнянь. Доведення с.504 [3] 4.9. Збалансовані дерева с. 146-180 [1], 523-562 [3] Рішення задачі стабілізації продуктивності для реалізацій, заснованих на використанні BST-дерев, можна знайти, використовуючи будь-який з трьох базових підходів до забезпечення продуктивності при розробці алгоритмів: амортизацію, рандомізацію і оптимізацію. При використанні рандомізованого підходу ухвалення випадкового рішення вбудовано в сам алгоритм, що радикально зменшує вірогідність виникнення гіршого випадку сценарію (незалежно від вхідних даних). Оптимізаційний підхід полягає в забезпеченні гарантованої продуктивності кожної операції. Ці методи вимагають зберігання у деревах деякої структурної інформації, і, як правило, їх реалізація пов'язана з певною складністю. 4.8.1. Розширені BST-дерева с. 528-540 [3] Один з підходів до підвищення ступеня збалансованості в BST-деревах пов'язаний з періодичним явним виконанням їх повторного балансування. З одного боку, між операціями повторного балансування час вставки для даної послідовності ключів може зростати в квадратичній залежності від довжини послідовності; з іншого боку, повторне балансування крупних дерев небажано виконувати дуже часто, оскільки для виконання кожної операції балансування потрібний час, який, щонайменше, лінійно залежить від розміру дерева. Ротації використовуються як для переміщення вузлів по дереву так і для запобігання розбалансування дерев. h(b) – h(L) = 2 та h(C) h(R). Великий правий оберт – використовується, коли h(b) - h(L) = 2 та h(c) > h(R). h(b) – h(R) = 2 та h(C) h(L). Великий лівий оберт – використовується, коли h(b) - h(R) = 2 та h(c) > h(L). У стандартній реалізації BST-дерев кожен новий вставлений елемент потрапляє в нижню частину дерева, створюючи якийсь зовнішній вузол (листок). Існує інший метод вставки, при якому кожен новий елемент вставляється в корінь, і тому недавно вставлені вузли знаходяться поблизу кореня дерева. Побудовані таким чином дерева мають ряд цікавих властивостей:
На цій схемі показаний результат (внизу) ротації вліво у вузлі S в прикладі BST-дерева (вгорі). Вузол, S переміщається в дереві вниз, стаючи правим дочірнім вузлом свого колишнього лівого дочірнього вузла. Ротація виконується шляхом отримання зв'язку з новим коренем Е з лівого зв'язку S, установки лівого зв'язку S шляхом копіювання правого зв'язку Е, установки правого зв'язку Е, вказуючого на S, і установки зв'язку з А, вказуючого не на S, а на Е. Ефект ротації полягає в переміщенні Е і його лівого піддерева на один рівень вгору і переміщення S і його правого піддерева на один рівень вниз. Решта дерева залишається незмінною. На цій схемі показаний результат (внизу) ротації вправо вузла А в прикладі BST- дерева (вгорі). Вузол, що містить А, переміщається вниз, стаючи лівим дочірнім вузлом свого колишнього правого дочірнього вузла. Ротація виконується за рахунок отримання зв'язку з новим коренем Е з правого зв'язку А, установки правого зв'язку А шляхом копіювання лівого зв'язку Е, установки лівого зв'язку Е на А і установки зв'язку з А (верхній зв'язок дерева) натомість на Е. Вставка в корінь дерева вузла G Ця послідовність відображає результат вставки G в BST-дерево, приведене на верхньому малюнку, після (рекурсивного) виконання ротації після вставки з метою переміщення вставленого вузла G в корінь. Цей процес еквівалентний вставці G з подальшим виконанням послідовності ротацій для переміщення його в корінь. ключів A S E R C Н I N G X M P L в спочатку порожнє BST-дерево. Кожен новий вузол вставляється в корінь із зміною зв'язків, розташованих уздовж його шляху пошуку, що приводить до утворення відповідного BST- дерева. 4.8.2. Рандомізовані дерева с. 527-540 [3] "Випадковість" можна включити в алгоритм, щоб ця властивість зберігалася без будь-яких допущень щодо порядку вставки елементів. Ідея вельми проста: при вставці нового вузла у дерево, що складається з N вузлів, вірогідність появи нового вузла в корені повинна бути рівна 1/(N+1), тому просто приймаємо рандомізоване рішення використовувати вставку в корінь з цією вірогідністю. Це просте імовірнісне об'єднання стандартного алгоритму BST-дерева з методом вставки в корінь забезпечує стабільну в сенсі вірогідності продуктивність. Доведення в (с.527 [3]) Переваги: Переваги:
с. 540-545 [3] Для гарантії того, що створювані BST-дерева будуть збалансованими, структури дерев повинні володіти певною гнучкістю. Для отримання подібної гнучкості припустимо, що вузли в деревах можуть містити більш за один ключ. Зокрема, припускаємо існування 3-вузлів і 4-вузлів, які можуть містити, відповідно два і три ключі. Збалансоване 2-3-4-дерево пошуку - це 2-3-4-дерево пошуку, всі порожні піддерева якого розташовані на однаковій відстані від кореня. На малюнку зображено 2-3-4-дерево, що містить ключі ASRCHINGEXMPL. В такому дереві ключ можна відшукати, використовуючи ключі вузла, розташованого в корені, для знаходження зв'язку до піддерева, а потім продовжити рекурсивне виконання пошуку. Наприклад, для пошуку ключа P в цьому дереві потрібно спускатися вправо від кореня, оскільки P більше I, потім по середній гілці правого піддерева, оскільки значення P знаходиться між N та R, і, нарешті, завершити пошук у вузлі з ключем P. Основна особливість 2-3-4-дерева полягає в тому, що можна виконувати вставки завжди зберігаючи повну збалансованість дерева. Якщо пошук уривається на 3-вузлі, його досить перетворити в 4-вузол. Кожний 4-вузол, що зустрічається на шляху пошуку, розділяється, забезпечуючи тим самим вільне місце для нового елемента в нижній частині дерева. Кожен зовнішній вузол розташовується на однаковій відстані від кореня: виконувані перетворення не роблять ніякого впливу на відстань між будь-яким вузлом і коренем, за винятком випадку коли виконується розділення кореня (в цьому випадку відстань між всіма вузлами і коренем збільшується на 1). Якщо всі вузли є 2-вузлами, приведене твердження також справедливо, оскільки дерево подібно до повного бінарного дерева; якщо в дереві присутні 3- і 4-вузли, висота може бути тільки менше. Доведення в (с.543 [3]) У самому гіршому випадку всі вузли на шляху до місця вставки є 4-вузлами і вони всі будуть розділені. Але в дереві, утвореному в результаті випадкових перестановок N елементів, маловірогідний не тільки цей гірший випадок, але і в середньому, ймовірно, буде потрібно менше операцій розділення, оскільки в деревах 4-вузли зустрічаються не так часто. Доведення в (с.543 [3]) Цей підхід веде до більшої кількості операцій розділення вузлів під час виконання алгоритму, але його простіше програмувати, оскільки доводиться враховувати менше випадків. Спочатку в дереві виконується пошук з метою знаходження розташованого в нижній частині дерева вузла, якому повинен належати елемент, що вставляється. Якщо цей вузол є 2-вузлом або 3-вузлом, він перетвориться в 3-вузол або 4-вузол, як описувалося раніше. Якщо він - 4-вузол, він ділиться, як і раніше (зі вставкою нового елементу в один з результуючих 2-вузлів в нижній частині), і середній елемент вставляється в батьківський вузол якщо той є 2- або 3-вузлом. Якщо батьківський вузол є 4-вузлом, він ділиться на два (зі вставкою середнього вузла у відповідний 2-вузол), а середній елемент вставляється в його батьківський вузол, якщо той є 2- або 3-вузлом. Якщо вузол предок також є 4-вузлом, ми продовжуємо такий підйом по дереву, розділяючи 4-вузли до тих пір, поки на шляху пошуку не зустрінеться 2-вузол або 3-вузол. 4.8.4. Червоно-чорні дерева с. 545-555 [3] Спроба позбавитися від цього недоліку привела до появи червоно-чорних дерев бінарного пошуку. У будь-якому дереві кожен вузол вказується одним зв'язком, тому фарбування зв'язків еквівалентне фарбуванню вузлів. Відповідно, використовуємо по одному додатковому розряду на кожен вузол для зберігання кольору зв'язку, вказуючого на цей вузол. 2-3-4-дерева, представлені таким чином називаються червоно-чорними (або RB-) деревами бінарного пошуку. 4-вузол (вгорі зліва) представляється збалансованим піддеревом, що складається з трьох 2-вузлів, які сполучені R-зв'язками (вгорі справа). Обидва уявлення мають три ключі і чотири В-зв'язки. 3-вузол (внизу зліва) представляється одним 2-вузлом, пов'язаним з іншим вузлом (зліва або справа) єдиним R-зв'язком (внизу справа). Обидва уявлення мають два ключі і три В-зв'язки. 2-3-4-дерево 2-3-4-дерево відповідне йому RB-дерево Збалансоване RB-дерево бінарного пошуку - це RB-дерево бінарного пошуку, в якому всі шляхи від зовнішніх вузлів до кореня містять однакову кількість чорних зв'язків.
Вихідне дерево Процес вставки складається з розділення 4-вузла С зі зміною кольору та наступним додаванням нового 2-вузла в нижній частині та перетворенням вузла, що містить ключ Н в 3-вузол. Вихідне дерево Процес вставки складається з розділення 4-вузла І зі зміною кольору, додавання нового 2-вузла в нижній частині дерева та виконання (з поверненням до кожного вузла на шляху пошуку після викликів рекурсивних функцій) ротації вліво у вузлі С і ротації вправо у вузлі R з метою завершення процесу розділення 4-вузла. Тільки для розділень, які в 2-3-4-дереві відповідають 3-вузлу, сполученому з 4-вузлом, потрібна ротація в RB-дереві; найгірший випадок виникає тоді, коли шлях до точки вставки складається з 3-вузлів і 4-вузлів, що чергуються. Лема 8. Для пошуку в RB-дереві з N вузлами, побудованому з випадкових ключів, в середньому використовується біля 1.002 log N порівнянь. Доведення в (с.550 [3]) 4.8.5. Інші дерева пошуку с. 158-165 [1], 551-553 [3], 652-663 [3] Для цих дерев характерно, що висоти двох піддерев кожного вузла розрізняються максимум на 1. Якщо вставка призводить до того, що висота одного з піддерев якого-небудь вузла збільшується на 1, умова балансу може бути порушена. Проте, одна одиночна або подвійна ротація у будь-якому випадку поверне вузол в збалансований стан. Для ухвалення рішення про те, які ротації потрібно виконувати (якщо це необхідно), потрібно знати, чи є висота кожного вузла на 1 менше, рівна або на 1 більше висоти його спорідненого вузла. Для прямого кодування цієї інформації потрібно по два розряди на кожен вузол, хоча, використовуючи RB-абстракцію, можна обійтися і без використання додаткового об'єму пам'яті. Приклад. АВЛ-дерево 2-3-дерева не володіють достатньою гнучкістю, щоб можна було побудувати зручний алгоритм низхідної вставки. Крім того, RB-структура може спростити реалізацію, але висхідні 2-3-дерева не забезпечують особливих переваг порівняно з висхідними 2-3-4-деревами, оскільки для підтримки балансу як і раніше потрібні одиночні і подвійні ротації. Висхідні 2-3-4-дерева дещо краще збалансовані і володіють тою перевагою, що для кожної вставки потрібна максимум одна ротація. Приклад. 2-3-дерево Приклад. 2-3-дерево Приклад. В-дерево 4.9. Навантажені дерева В оригіналі структура називається trie, це слово отримане з букв, що стоять в середині слова "retrieval" (пошук, вибірка, повернення). Література для самостійного читання: с. 152-157 [1], 608-645 [3] Структура навантажених дерев підтримує оператори множин: вставка, видалення, очищення, друк. У навантаженому дереві кожен шлях від кореня до листа відповідає одному слову з множини. При такому підході вузли дерева відповідають префіксам слів множини. Щоб уникнути колізій слів, подібних THE і THEN, вводиться спеціальний символ $, маркер кінця, що вказує закінчення будь-якого слова. Тоді тільки слова будуть словами, але не префікси. Тут корінь відповідає порожньому рядку, а два його сина - префіксам Т і S. Найлівіший лист представляє слово THE, наступний лист - слово THEN і т.д. type chars = {'А', 'В', . . ., 'Z', '$' } ; TRIENODE = array[chars] of ^TRIENODE; З прикладом реалізації можна ознайомитись в (с.154 [1]). Домашнє завдання Домашнє завдання Підготуватися до виконання практичної роботи №5. Підготуватися до контрольної роботи (типові питання можна подивитися в завданнях до практичних робіт №4,5). |