Видалення з дерева бінарного пошуку 1
У книзі детально розглядаються базові поняття алгоритмів і основоположні структури даних, алгоритми сортування, пошуку, хеширования, синтаксичного розбору, стиснення даних, а також багато інших тем, тісно пов'язані з прикладним програмуванням. Достаток ретельно перевірених прикладів коду істотно прискорює не тільки освоєння фундаментальних алгоритмів, але також і сприяє більш кваліфікованому підходу до повсякденного програмування.
Незважаючи на те що книга розрахована в першу чергу на професійних розробників додатків на Delphi, вона надасть безсумнівну користь і початківцям програмістам, демонструючи їм прийоми і трюки, які настільки популярні у справжніх «профі». Всі коди прикладів, згадані в книзі, доступні для вивантаження на Web-сайті видавництва.
Книга: Фундаментальні алгоритми та структури даних в Delphi
Видалення з дерева бінарного пошуку
Видалення з дерева бінарного пошуку
Як і при виконанні попередньої операції, велика частина проблем може бути прихована від користувача дерева бінарного пошуку. Однак дерево має виконати певну, більш складне завдання.
Природно, першим кроком є пошук елемента в дереві із застосуванням стандартного алгоритму. Якщо знайти елемент не вдасться, доведеться якось повідомити про невдачу. У разі виявлення елемента, пошук може бути перерваний у вузлі одного з трьох типів, як це має місце в стандартному бінарному дереві.
Перший тип вузла - вузол без дочірніх вузлів, обидві дочірні зв'язку якого є нульовими. Інакше кажучи, лист. Щоб видалити вузол цього типу, ми просто розриваємо його зв'язок з батьківським вузлом і видаляємо його. Це видалення не порушує порядок вузлів у дереві - в кінці кінців, вузол був листом і не мав дочірніх вузлів.
Другий тип вузла - вузол тільки з одним дочірнім вузлом. У разі стандартного бінарного дерева ми просто переміщаємо дочірній вузол на один рівень вгору, щоб замінити видаляється вузол. Чи можна це ж зробити в даному випадку? Розглянемо батьківський вузол вузла, який повинен бути знищений. Віддалений вузол є або лівим дочірнім вузлом (в цьому випадку його ключ менше ключа батьківського вузла), або правим дочірнім вузлом (в цьому випадку його ключ більше ключа батьківського вузла). Не тільки цей вузол, а й всі дочірні, "внучаті" і так далі вузли віддаленого вузла володіють тим же властивістю. Всі вони будуть або менше батьківського вузла, або більше. Таким чином, до тих пір, поки мова йде про батьківський вузлі, при заміні вузла одним з його дочірніх вузлів властивість упорядкування буде зберігатися. Якщо дочірній вузол має свої дочірні вузли, це переміщення не позначається на них або на їх порядку. Отже, в разі дерева бінарного пошуку ми як і раніше можемо виконати цю просту операцію.
Третій тип вузла - вузол з двома дочірніми вузлами. У стандартному дереві бінарного пошуку ми вважали спробу видалення вузла цього типу помилкою. Видалення не могло бути виконано, оскільки не існувало ніякого загального способу виконання операції видалення, який мав би сенс. У разі дерева бінарного пошуку це не так: в даному випадку можна скористатися властивістю впорядкування дерева бінарного пошуку.
Ситуація виглядає наступним чином: нам потрібно видалити певний вузол (тобто елемент в цьому вузлі), але він має два дочірніх вузла (кожен з яких має власні дочірні вузли). Алгоритм видалення настільки складним, тому спочатку він буде описаний словесно, а потім буде показано, як він працює. На практиці ми шукаємо вузол, що містить найбільший елемент, який менше тільки того, який ми намагаємося видалити. Потім ми міняємо місцями елементи в цих двох вузлах. І, нарешті, ми видаляємо другий вузол. Він завжди буде відповідати одному з раніше розглянутих випадків видалення.
Перший крок полягає в знаходженні найбільшого елемента, меншого того елемента, який ми намагаємося видалити. Зрозуміло, що він знаходиться в лівому дочірньому дереві (всі елементи цього дерева менше видаляється елемента). Крім того, він є найбільшим елементом цього дерева. Інакше кажучи, всі інші елементи, які можуть перебувати в лівому дочірньому дереві, менше цього елементу. Насправді все елементи в правому дочірньому дереві більше цього вибраного елемента (оскільки він менше елемента, який повинен бути видалений, а цей елемент, в свою чергу, менше всіх елементів в правому дочірньому дереві). Отже, він цілком може замінити видаляється елемент, і ця дія не порушить порядок елементів в дереві.
Але як щодо вузла, з позиції якого він був переміщений, і який тепер потрібно видалити? Відносно цього конкретного вузла важливо усвідомити, що він не має ніякого правого дочірнього вузла. Якби він мав правий дочірній вузол, елемент в дочірньому вузлі мав би бути більше елемента, з яким ми поміняли його місцями, і, отже, спочатку обраний елемент не міг би бути найбільшим. Він може мати лівий дочірній вузол, але незалежно від цього ми знаємо, як видалити вузол, який має не більше одного дочірнього вузла.
При цьому все ще залишається проблема виявлення найбільшого елемента, який менше вихідного, призначеного для видалення. По суті, ми виконуємо переміщення по дереву. Починаючи з елемента, який потрібно видалити, ми переходимо до лівої дочірньої зв'язку. З цього місця ми продовжуємо переміщатися по правим дочірнім зв'язків до тих пір, поки не доберемося до вузла, що не має ніякої правої дочірньої зв'язку. Цей елемент гарантовано містить найбільший елемент, менший тільки того елемента, який ми намагаємося видалити.
Зверніть також увагу, що видалення, як і вставка, може призводити до створення виродженого дерева. Цю проблему вирішують алгоритми балансування, які ми розглянемо при ознайомленні з червоно-чорним варіантом дерева бінарного пошуку.
Лістинг 8.15. Видалення з дерева бінарного пошуку
function TtdBinarySearchTree.bstFindNodeToDelete (aItem. pointer)