НОУ ІНТУІТ, Лекція, Алгоритми пошуку на основі дерев
Оптимальні дерева
У двійковому дереві пошук одних елементів може відбуватися частіше, ніж інших, тобто існують ймовірності пошуку p k-го елемента і для різних елементів ці ймовірності неоднакові. Можна припустити, що пошук у дереві в середньому буде швидше, якщо ті елементи, які шукають частіше, будуть знаходитися ближче до кореня дерева.
Нехай дані 2n+1 ймовірностей p1, p2. pn, q0, q1. qn , де pi - ймовірність того, що аргументом пошуку є елемент Ki; qi – ймовірність того, що аргумент пошуку лежить між вершинами Ki та Ki+1; q0 - ймовірність того, що аргумент пошуку менше, ніж значення елемента K1; qn - ймовірність того, що аргумент пошуку більше, ніж Kn. Тодіціна дерева пошукуC визначатиметься таким чином:
де – рівень вузла j, а – рівень аркуша K .
Дерево пошуку називаєтьсяоптимальним, якщо його ціна мінімальна. Тобтооптимальне бінарне дерево пошуку- це бінарне дерево пошуку, побудоване для забезпечення максимальної продуктивності при заданому розподілі ймовірностей пошуку необхідних даних.
Існує підхід побудови оптимальних дерев пошуку, у якому елементи вставляються порядку зменшення частот, що у середньому непогані дерева пошуку. Однак цей підхід може дати вироджене дерево пошуку, яке буде далеким від оптимального. Ще один підхід полягає у виборі кореня k таким чином, щоб максимальна сума ймовірностей для вершин лівого піддерева або правого піддерева була настільки мала, наскільки це можливо. Такий підхід також може бути поганим у разі вибору як корінь елемента з малим значенням pk.
Існують алгоритми, які дозволяють збудуватиоптимальне дерево пошуку. До них належить, наприклад, алгоритм Гарсія-Воча. Однак такі алгоритми мають тимчасову складність порядку O(n 2 ). Таким чином, створення оптимальних дерев пошуку вимагає великих витрат, що не завжди виправдовує виграш при швидкому пошуку.
Збалансовані по висоті дерева
У гіршому випадку, коли дерево вироджене в лінійний список, зберігання даних у впорядкованому бінарному дереві жодного виграшу в складності операцій порівняно з масивом або лінійним списком не дає. У кращому випадку, коли дерево збалансоване, для всіх операцій виходить логарифмічна складність, що набагато краще.Ідеально збалансованимназивається дерево, у якого для кожної вершини виконується вимога: число вершин у лівому та правому піддерев'ях відрізняється не більше ніж на 1.
Однак ідеальну збалансованість досить важко підтримувати. У деяких випадках при додаванні або видаленні елементів може знадобитися значна перебудова дерева, що не гарантує логарифмічної складності. У 1962 році два радянські математики: Г.М. Адельсон-Вельський та Є.М. Ландіс – ввели менш суворе визначення збалансованості та довели, що при такому визначенні можна написати програми додавання та/або видалення, що мають логарифмічну складність та зберігають дерево збалансованим. Дерево вважаєтьсязбалансованим по АВЛ(скорочення від прізвищ Г.М. Адельсон-Вельський та Е.М. Ландіс), якщо для кожної вершини виконується вимога: висота лівого та правого піддерев'я різняться не більше, ніж на 1. Не всяке збалансоване по АВЛ дерево ідеально збалансоване, але всяке ідеально збалансоване дерево збалансоване по АВЛ.
При операціях додавання та видалення може відбутися порушеннязбалансованості дерева. У цьому випадку будуть потрібні деякі перетворення, які не порушують упорядкованості дерева і сприяють кращій збалансованості.
Розглянемо такі перетворення. Нехай вершина a має правий нащадок b. Позначимо через P ліве піддерево вершини a через Q і R - ліве і праве піддерев'я вершини b відповідно. Впорядкованість дерева вимагає, щоб P. Так само вимагає впорядкованість дерева з коренем b , його лівим нащадком a , в якому P і Q - ліве і праве піддерев'я вершини a , R - праве поддерево вершини b . Тому перше дерево можна перетворити на друге, не порушуючи впорядкованості. Таке перетворення називаєтьсямалим правим обертанням(рис. 40.3). Аналогічно визначається симетричне йому мале ліве обертання.
Нехай b – правий нащадок вершини a, c – лівий нащадок вершини b, P – ліве піддерево вершини a, Q та R – відповідно ліве та праве піддерева вершини c, S – праве піддерево b . Тоді P. Такий самий порядок відповідає дереву з коренем c, що має лівий нащадок a і правий нащадок b, для яких P і Q - піддерева вершини a, а R і S - піддерева вершини b. Відповідне перетворення називатимемовеликим правим обертанням(рис. 40.4). Аналогічно визначається симетричне йому велике ліве обертання.
Схематичноалгоритм додавання нового елемента в збалансоване по АВЛ деревоскладатиметься з наступних трьох основних кроків.
Крок 1. Пошук дерева.
Крок 2. Вставте елемент у місце , де закінчився пошук , якщо елемент відсутній.
Крок 3. Відновлення збалансованості.
Перший крок необхідний для того, щоб переконатися у відсутності елемента в дереві, а також знайти таке місце вставкипісля вставки дерево залишилося впорядкованим. Третій крок є зворотний прохід шляхом пошуку: від місця додавання до кореня дерева. У міру просування цим шляхом коригуються показники збалансованості прохідних вершин, і проводиться балансування там, де це необхідно. Додавання елемента до дерева ніколи не потребує більше одного повороту.
Алгоритм видалення елемента зі збалансованого деревавиглядатиме так:
Крок 1. Пошук дерева.
Крок 2. Видалення елемента з дерева.
Крок 3. Відновлення збалансованості дерева (зворотний прохід).
Перший крок необхідний, щоб знайти у дереві вершину, яка має бути видалена. Третій крок є зворотний прохід від місця, з якого взятий елемент для заміни видаляється, або від місця, з якого видалений елемент, якщо заміни не було необхідності. Операція видалення може вимагати перебалансування всіх вершин уздовж дороги до кореня дерева, тобто. порядку log n вершин. Таким чином, алгоритми пошуку, додавання та видалення елементів у збалансованому по АВЛ дереві мають складність, пропорційну O(log n).
Дерева цифрового (порозрядного) пошуку
Методи цифрового пошуку досить громіздкі та погано ілюструються. Розглянемо бінарне дерево цифрового пошуку. Як і в деревах, розглянутих вище, у кожній вершині такого дерева зберігається повний ключ, але перехід по лівій або правій гілки відбувається не шляхом порівняння ключа-еталона зі значенням ключа, що зберігається у вершині, а на основі значення чергового біта аргументу. Реалізація цифрового пошуку відбувається порозрядно (побітово).
Пошук починається з кореня дерева. Якщо ключ, що міститься в кореневій вершині, не збігається з аргументом пошуку, то аналізується найлівіший бітаргументу. Якщо він дорівнює 0, відбувається перехід лівою гілкою, якщо 1 – правою. Якщо виявляється збіг ключа з аргументом пошуку, то аналізується наступний біт аргументу тощо. Пошук завершується, коли будуть перевірені всі біти аргументу або зустрінеться вершина з відсутнім лівим або правим посиланням.
Ключові терміни
Бінарне дерево цифрового пошуку- це дерево, у кожній вершині якого зберігається повний ключ, а перехід по гілках відбувається на основі значення чергового біта аргументу.
Двійкове (бінарне) дерево- це ієрархічна структура, в якій кожен вузол має не більше двох нащадків.
Ідеально збалансоване дерево- це дерево, у якого для кожної вершини виконується вимога: число вершин у лівому та правому піддерев'ях відрізняється не більше ніж на 1.
Ключ пошуку- це поле, за значенням якого відбувається пошук.
Оптимальне бінарне дерево пошуку– це бінарне дерево пошуку, побудоване для забезпечення максимальної продуктивності при заданому розподілі ймовірностей пошуку необхідних даних.
Пошук- це процес знаходження конкретної інформації в раніше створеній безлічі даних.
Збалансоване по АВЛ дерево- це дерево, для кожної вершини якого виконується вимога: висота лівого та правого піддерев різняться не більше, ніж на 1.
Випадкові дерева пошуку– це впорядковані бінарні дерева пошуку, під час створення яких елементи вставляються у випадковому порядку.
Упорядковане двійкове дерево- це двійкове дерево, в якому для будь-якої його вершини x справедливі властивості: всі елементи в лівому піддереві менше елемента, що зберігається в x; всі елементи у правому піддереві більшеелемента, що зберігається в x; всі елементи дерева різні.
Частково впорядковане бінарне дерево – це впорядковане бінарне дерево, в якому трапляються однакові елементи.