Дерева розгалуження: Самоналаштовуване бінарне дерево пошуку

Чому дерево розгалуження самоналаштовується

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

Вигин у випадку з однією поворотом біля кореня

Найпростіший із трьох патернів розгалуження – це вигин, і він відбувається лише один раз на кожній операції розгалуження, безпосередньо в кінці ходи. Він застосовується, коли вузол, який розгалужують, є прямим сибідом кореня дерева, тобто немає потреби турбуватися про діда. У цій ситуації дерево виконує один поворот: якщо вузол – лівий син, дерево повертає праворуч навколо батька; якщо вузол – правий син, воно повертає ліворуч навколо батька. Ця одна дія міняє вузол і його батька, розміщуючи вузол на корені, а старий корінь перетворюється на його дитину, і піддерево, яке раніше висіло між ними, правильно приєднується, щоб зберегти порядок. Оскільки вигин відбувається лише тоді, коли вузол знаходиться на одному кроці від кореня, він діє як фінальний етап довшого розгалуження, яке могло вже пройти кілька кроків вигинів-вигинів або вигинів-заглибів глибше в дереві. Деякі операції розгалуження складаються лише з одного вигину, який відбувається, коли звернений до вузол був прямим сибідом кореня на початку. Хоча це найменш драматичний із трьох випадків, вигин є необхідним для правильності, оскільки без нього вузол на рівні нижче кореня не мав би способу завершити свій шлях до вершини.

Дзеркальне розташування: Прямі обертання

Дзеркальний випадок обробляє ситуацію, коли вузол і його батько нахилені в однакову сторону, тобто обидва є лівими дітьми відповідних батьків, або обидва є правими дітьми. Замість безпосереднього обертання вузла навколо свого батька першим, дзеркальний випадок обертає батька навколо дідуся першим, а потім лише обертає вузол навколо переміщеного батька, при цьому обидва оберти відбуваються в одному напрямку. Цей порядок має велике значення. Обертання більш віддаленої пари перед ближчою парою забезпечує хорошу довгострокову поведінку дерев сплайну, оскільки це зазвичай зменшує глибину вузлів вздовж шляху доступу приблизно вдвічі, а не просто переміщує проблему на рівень нижче, що стало бся, якби обертання виконувалися у простий верх-вниз порядок. Уявіть довгий ланцюг лівих дітей, що тягнуться вниз по лівій стороні дерева: дзеркальний випадок сплайну працює через цей ланцюг двома рівнями одночасно, кожна пара обертів руйнує частину ланцюга та розсіює залишки вузлів у більш поширеній, пухлій формі. Це робочий випадок для глибоко вбудованих вузлів, оскільки більшість реальних шляхів доступу не є суворим зигзагом, а містять пробіжки з однаковими кроками в одному напрямку, і дзеркальний випадок запобігає тому, щоб ці пробіжки призводили до найгірших випадків ланцюгів, які зберігаються при повторних операціях.

Заґрунтований випадок: протилежні обертання

Заґрунтований випадок охоплює іншу можливість, коли вузол і його батько нахиляються в протилежних напрямках, наприклад, коли вузол є лівим дитиною, а батько – правою; або навпаки. У цьому випадку дерево все ще виконує два обертання, але вони відбуваються у різних напрямках, а не в одному. Перше обертання піднімає вузол навколо свого негайного батька, а друге обертання потім піднімає той самий вузол навколо діда, ефективно піднявши вузол на два рівні, а батько та дідусь стають його двома дітьми з обох сторін. Візуально це схоже на подвійне обертання, яке використовується для виправлення дисбалансу в дереві AVL, і воно створює подібний ефект вирівнювання: замість зігнутого сходинкового шляху, зигзаг випрямляє локальну структуру так, що колишній батько та дідусь вузла стають братами під ним. Розгалуження вузла зазвичай передбачає роботу з сумішшю пар «зіг-заг» і «зіг-заг», коли шлях зигзагом або йде прямо в різних точках, а остання «зіг» застосовується лише якщо залишається один додатковий рівень після того, як вузол досягає негайного дитини кореня. Разом ці два подвійні обертальні випадки дозволяють одному операції розгалуження звести будь-який довгий шлях доступу до кореня одним проходом.

Чому це дає гарну середню продуктивність

Один окремий операція розгалуження на нещадному, погано сформованому дереві все ще може пройти довгий шлях, перш ніж знайдеться ціль, тому будь-який один доступ не гарантується як швидкий. Цінність сплейсних дерев полягає не в швидкості окремої операції, а в їх поведінці в середньому по багатьох операціях. Оскільки кожен доступ переміщує уражений вузол до кореня, вузол, який відвідується повторно, майже миттєво стає дешевшим для досягнення знову після свого першого, можливо, дорогого візиту. Послідовності операцій, які повторно торкаються одного й того ж невеликого набору гарячих елементів, значно швидші з часом, оскільки ці елементи кластеруються біля верхньої частини дерева, тоді як холодні елементи відсуваються вниз, де вони рідко втручаються. Математичний аналіз сплейсних дерев показує, що хоча окремі операції можуть бути дорогими, загальна вартість, сумарована по будь-якій довгій послідовності операцій, залишається пропорційною тому, що досягає добре збалансоване дерево, отже дорогі випадки ефективно оплачуються багатьма дешевими, які слідують за ними. Ця самоналаштовувана поведінка робить сплейсні дерева справді корисними поза класом. Деякі реалізації кешу використовують структури, подібні до сплейсних дерев, оскільки нещодавно та часто використовувані записи природно піднімаються так, щоб їх можна було знайти найшвидше. Деякі маршрутизатори мереж використовували їх для управління інформацією про маршрутизацію, де певний набір цілей домінує в трафіку. Алгоритми стиснення даних, включаючи деякі адаптивні схеми кодування, також беруть цю ідею запозиченою, оскільки вони отримують користь від дешевого повторного доступу до символів, які часто зустрічаються в потоці вхідних даних.

Часті запитання

Спробуйте наживо

Усе, що вище, працює прямо у вашому браузері — відкрийте Splay Trees: The Self-Adjusting Binary Search Tree і змінюйте параметри під час роботи. Нічого не встановлюється, нічого не завантажується на сервер, уся модель живе в одній вкладці.