НОУ ІНТУІТ, Лекція, Збалансовані дерева
Східні 2-3-4-дерева
Незважаючи на гарантію продуктивності, що забезпечується рандомізованими та скошеними BST-деревами, в обох випадках не виключається ймовірність того, що час виконання окремої операції пошуку буде лінійним. Отже, ці методи не допомагають відповісти на основне питання щодо збалансованих дерев: чи існує тип деревини BST, для якого можна гарантувати логарифмічну залежність часу виконання кожної операції вставити і знайти від розмірів дерева? У цьому та наступному розділах ми розглянемо абстрактне узагальнення BST-дерев та їх абстрактне уявлення у вигляді типу BST-дерева, які дозволяють ствердно відповісти на це питання.
Для гарантії збалансованості створюваних BST-дерев використовувані структури дерев повинні мати певну гнучкість. Для отримання такої гнучкості припустимо, що вузли наших дерев можуть містити більше одного ключа. А саме, ми припустимо існування 3-вузлів та 4-вузлів, які можуть містити, відповідно, два та три ключі. 3-вузли містять три посилання: одна на всі елементи, ключі яких менше обох його ключів, одна на всі елементи, ключі яких мають значення між двома його ключами, і одна на всі елементи, ключі яких більше обох його ключів. Аналогічно, 4-вузол має чотири посилання: по одному для кожного з інтервалів, визначених його трьома ключами. Тоді вузли в стандартному BST-дереві можна було б називати двома вузлами: вони містять один ключ і два посилання. Пізніше ми розглянемо ефективні способи визначення та реалізації базових операцій із цими розширеними вузлами; Поки будемо вважати, що є зручні способи роботи з ними, і подивимося, як вони дозволяють формувати дерева.
Визначення 13.2.Збалансоване 2-3-4-дерево пошуку – це 2-3-4-дерево пошуку, всі посилання на порожні дерева якого розташовані на однаковій відстані від кореня.
У цьому розділі термін 2-3-4-дерево буде застосовуватися до збалансованих 2-3-4-дерев пошуку (в інших контекстах він означає більш загальну структуру). Приклад 2-3-4-дерева наведено на рис. 13.10.
Алгоритм пошуку ключів у такому дереві є узагальнення алгоритму пошуку для BST-дерев. Щоб з'ясувати, чи знаходиться ключ у дереві, ми порівнюємо його з ключами докорінно: якщо він дорівнює кожному з них, пошук успішний; в іншому випадку ми переходимо за посиланням від кореня до піддерева, що відповідає безлічі значень ключів, до якого належить шуканий ключ, а потім рекурсивно виконуємо пошук у цьому дереві. Існує ряд способів подання 2-, 3- та 4-вузлів та організації пошуку відповідного посилання; ми відкладемо розгляд цих рішень до розділу 13.4, де буде розглянуто дуже зручне рішення.
Для вставки нового вузла в 2-3-4-дерево можна було б, як у BST-деревах, виконати невдалий пошук, а потім приєднати вузол, але при цьому нове дерево виявилося б незбалансованим. Основна причина важливості 2-3-4-дерев полягає в тому, що вони дозволяють виконувати вставки, завжди зберігаючи повну збалансованість дерева. Наприклад, легко бачити, що робити, якщо пошук закінчується на 2-вузлі: достатньо перетворити його на 3-вузол. Аналогічно, якщо пошук закінчується на 3-вузлі, його достатньо перетворити на 4-вузол. Але що робити, якщо пошук переривається на 4-вузлі? Рішення полягає в тому, що можна знайти місце для нового ключа, зберігаючи збалансованість дерева, спочатку розділивши 4-вузол на два 2-вузли, і потім передавши середній вузол до батьківського вузла. Ці три описані випадки показані на рис.13.11.
А що робити, якщо необхідно розбити 4-вузол, батьківський вузол якого також є 4-вузлом? Одним із можливих виходів було б розбиття та батьківського вузла, але вузол-предок також може виявитися 4-вузлом тощо. — можливо, довелося б розділяти вузли по всьому шляху вгору по дереву. Простіший підхід — забезпечити, щоб шлях пошуку не завершувався у 4-вузлі, розбиваючи будь-який 4-вузол, що трапляється при прямуванні вниз по дереву.
Спускаючись вниз по дереву, не потрібно турбуватися про те, що батьківський вузол поточного вузла є 4-вузлом: адже виконувані перетворення забезпечують, що при проходженні кожного вузла в дереві ми потрапляємо у вузол, який не є нащадком 4-вузла. Зокрема, при досягненні нижньої частини дерева ми опиняємося не в 4-вузлі і можемо вставити новий вузол, безпосередньо перетворивши 2-вузол на 3-вузол, або 3-вузол на 4-вузол. Вставку можна вважати розбиттям уявного 4-вузла в нижній частині дерева, що передає вгору новий ключ.
Ще один нюанс: коли корінь дерева стає 4-вузлом, ми просто розбиваємо його, перетворюючи на трикутник, що складається з трьох 2-вузлів, як для першого вузла, що розбивається, в попередньому прикладі. Розбиття кореня після вставки дещо зручніше за очікування чергової вставки для виконання розбиття, оскільки в цьому випадку не потрібно піклуватися про батьківський вузл кореня. Розбиття кореня (і ця операція) призводить до збільшення висоти дерева однією рівень.
На цьому малюнку зображено 2-3-4-дерево, що містить ключі A S R C H I N G E X M P L .
У такому дереві ключ можна знайти, використовуючи ключі в кореневому вузлі для знаходження посилання на потрібне піддерево, з наступним рекурсивним продовженням пошуку. Наприклад, для пошуку ключа P у цьому дереві потрібно пройти праворуч від кореня,оскільки P більше I, потім - за середнім посиланням від правого дочірнього вузла кореня, оскільки P знаходиться між N і R, і, нарешті, завершити успішний пошук у 2-вузлі, що містить ключ P.
2-3-4-дерево, що складається тільки з 2-вузлів, аналогічно BST-дереву (вгорі). Ключ C можна вставити, перетворивши 2-вузол, в якому переривається пошук C, на 3-вузол (другий зверху малюнок). Аналогічно можна вставити ключ H, перетворивши 3-вузол, в якому переривається його пошук, на 4-вузол (третій зверху малюнок). Але вставка ключа I виконується складніше, оскільки його пошук переривається у 4-вузлі. Ми розбиваємо 4-вузол, передаємо його середній ключ батьківському вузлу, і перетворимо цей вузол на 3-вузол (четвертий зверху малюнок у рамці). Таке перетворення створює допустиме 2-3-4-дерево, у нижній частині якого з'являється місце для I . І, нарешті, ми вставляємо I в 2-вузол, на якому тепер переривається пошук, і перетворимо цей вузол на 3-вузол (нижній малюнок).
У 2-3-4-дереві будь-який 4-вузол, який не є дочірнім вузлом 4-вузла, можна розбити на два 2-вузли, передавши його середній запис батьківському вузлу. 2-вузол з дочірнім 4-вузлом (вгорі зліва) стає 3-вузлом з двома дочірніми 2-вузлами (вгорі справа), а 3-вузол з дочірнім 4-вузлом (внизу зліва) стає 4-вузлом з двома дочірніми 2-вузлами (Внизу праворуч).
Тут показаний результат вставки елементів з ключами A S E R C H I N G X спочатку порожнє 2-3-4-дерево. Кожен 4-вузол, що зустрічається по шляху пошуку, розбивається, забезпечуючи вільне місце для нового елемента в нижній частині дерева.
На рис. 13.13 показано побудову 2-3-4-дерева послідовною вставкою набору ключів. На відміну від стандартних BST дерев, які розростаються вниз від вершини, ці дерева ростуть знизу вгору. Оскільки 4-вузли розбиваються нашляхи від вершини вниз, такі дерева називаються низхідними 2-3-4-деревами. Цей алгоритм важливий, оскільки він створює практично ідеально збалансовані дерева пошуку, хоча в процесі проходження по дереву виконується лише кілька локальних перетворень.
Лемма 13.6.При пошуку в 2-3-4-деревах з N вузлів відвідується максимум lgN+1 вузлів.
Кожен зовнішній вузол знаходиться на однаковій відстані від кореня: перетворення, що виконуються, не мають жодного впливу на відстань між будь-яким вузлом і коренем, за винятком випадку, коли виконується розбиття кореня (у цьому випадку відстань між усіма вузлами і коренем збільшується на 1). Якщо всі вузли є 2-вузлами, наведене твердження справедливе, оскільки таке дерево подібне до повного бінарного дерева; якщо в дереві присутні 3- та 4-вузли, висота може бути тільки меншою.
Лемма 13.7.Для вставок у 2-3-4-деревах з N вузлів потрібно розбиття менше lg N + 1 вузлів у гіршому випадку і, швидше за все, менше одного розбиття вузла в середньому.
У найгіршому випадку всі вузли на шляху до точки вставки є 4-вузлами, і все буде потрібно розбити. Але в дереві, побудованому з випадкової перестановки N елементів, малоймовірний не лише цей найгірший випадок, але й у середньому, ймовірно, знадобиться дуже мало операцій розбиття, оскільки 4-вузли в деревах зустрічаються не так часто. Наприклад, у великому дереві на рис. 13.14 рис. 13.14 всі 4-вузли, крім двох, розташовані на нижньому рівні. До цього часу фахівцям не вдавалося аналітично точно проаналізувати продуктивність 2-3-4-дерев, але з емпірично отриманих результатів видно, що для балансування дерев використовується дуже мало розбиття. Найгірший випадок дорівнює лише lg N, а в практичних ситуаціях і він недосяжний.
Наведеного опису достатньо визначення алгоритму пошуку з використанням 2-3-4-дерев, який гарантує досить високу продуктивність у гіршому випадку. Однак ми знаходимося лише на півдорозі до реалізації. Можна написати алгоритми, що дійсно виконують перетворення з різними типами даних, що представляють 2-, 3- і 4-вузли, але в більшості завдань реалізація такого безпосереднього уявлення не дуже зручна. Як і у разі скошених BST-дерев, додаткові витрати на обробку складніших вузлів можуть зробити алгоритми повільнішими, ніж стандартний пошук по BST-дереву. Головне призначення балансування — страховка від найгіршої нагоди, але хотілося б, щоб витрати, пов'язані з цим, були низькими, і щоб не було додаткових витрат при кожному виконанні алгоритму. На щастя, як буде показано в розділі 13.4, існує досить просте уявлення 2-, 3- та 4-вузлів, яке дозволяє виконувати перетворення однотипним способом за невеликих додаткових витрат у порівнянні зі стандартним пошуком у бінарному дереві.
Це 2-3-4-дерево – результат 200 випадкових вставок у спочатку порожнє дерево. Всі шляхи пошуку у дереві містять не більше шести вузлів.
Описаний алгоритм — лише один із можливих способів підтримки балансу в 2-3-4-деревах пошуку. Розроблено й деякі інші методи, що дозволяють досягти таких самих результатів.
Наприклад, можна балансувати знизу вгору. Спочатку в дереві виконується пошук розташованого в нижній частині дерева вузла, якому повинен належати елемент, що вставляється. Якщо цей вузол є 2-вузлом або 3-вузлом, він перетворюється на 3-вузол або 4-вузол, як описано раніше. Якщо це 4-вузол, він розбивається, як і раніше (зі вставкою нового елементаодин з результуючих 2-вузлів у нижній частині), і середній елемент вставляється в батьківський вузол, якщо той є 2- або 3-вузлом. Якщо батьківський вузол є 4-вузлом, він також розбивається (зі вставкою середнього вузла з нижнього рівня у відповідний 2-вузол), а середній елемент вставляється до його батьківського вузол, якщо той є 2- або 3-вузлом. Якщо вузол-дід також є 4-вузлом, ми продовжуємо цей підйом по дереву, розбиваючи 4-вузли, поки на шляху пошуку не зустрінеться 2-вузол або 3-вузол.
Такий вид висхідного балансування можна виконувати в деревах, які містять лише 2- або 3-вузли (і не мають 4-вузлів). Цей підхід веде до більшої кількості операцій розбиття вузлів під час виконання алгоритму, але його простіше програмувати, оскільки доводиться враховувати менше випадків. Ще один підхід зменшує кількість розбиття вузлів, відшукуючи перед розбиттям 4-вузла його споріднені вузли, що не є 4-вузлами.
Як буде показано в розділі 13.4, реалізації всіх цих методів ґрунтуються на одній і тій самій рекурсивній схемі. У "Зовнішньому пошуку" також будуть розглянуті узагальнення цих методів. Основна перевага аналізованого низхідного підходу в порівнянні з іншими методами полягає в тому, що необхідна збалансованість може бути досягнута в результаті одного низхідного проходу по дереву.
13.39. Намалюйте збалансоване 2-3-4-дерево пошуку, утворене низхідними вставками елементів з ключами E A S Y Q U T I O N у вказаному порядку спочатку порожнє дерево.
13.40. Намалюйте збалансоване 2-3-4-дерево пошуку, утворене висхідними вставками елементів з ключами E A S Y Q U T I O N у вказаному порядку спочатку порожнє дерево.
13.41. Яка мінімальна та максимальна можлива висотазбалансованих 2-3-4-дерев, що містять N вузлів?
13.42. Яка мінімальна та максимальна можлива висота збалансованих 2-3-4-дерев бінарного пошуку, що містять N вузлів?
13.43. Намалюйте всі структурно різні збалансовані 2-3-4-дерева бінарного пошуку, що містять N ключів для .
13.44. Знайдіть ймовірність того, що кожне з дерев, намальованих у вправі 13.43, є результатом вставки N випадкових різних елементів спочатку порожнє дерево.
13.45. Складіть таблицю, що містить кількість ізоморфних дерев з вправи 13.43 для кожного значення N - у тому сенсі, що вони можуть бути перетворені одне в інше шляхом обміну піддерев у вузлах.
13.46. Опишіть алгоритми пошуку та вставки у збалансовані 2-3-4-5-6-дерева пошуку.