Дерево з посиланнями та зрізами

Проблема: Дерева, що змінюють форму

Зросло дерево є знайомою структурою: ієрархія, де кожна вершина, крім кореня, має рівно одного батька, а дерево визначає природне поняття роду, глибини та шляхів між вершинами. Багато алгоритмів покладаються на дерева, які будуються один раз і потім повторно запитуються, такі як бінарне дерево пошуку для пошуків або сегментне дерево для запитів діапазону. Але велика категорія проблем потребує чогось іншого: ліс дерев, який повторно переструктурується з часом. Дві операції визначають цю потребу. Операція зв’язку приєднує корінь одного дерева як дитину в іншому дереві, об'єднуючи два дерева в одне. Операція розрізання видаляє ребро між вершиною та її батьківським вузлом, розділяючи одне дерево на два. Між цими оновленнями ми все ще хочемо відповідати на запитання, такі як: який корінь дерева цієї вершини зараз, чи перебувають дві вершини в одному дереві або який мінімальний або максимальний вага ребра на шляху між двома вершинами. Якщо б ми використовували звичайне представлення дерева з явними покажчиками батьків і, скажімо, масив глибин або таблиці предків, одне розрізання глибоко в великому дереві могло б змусити перерахувати глибини та інформацію про предків для всього піддерева, що займає лінійний час у найгіршому випадку. Повторення цього через багато операцій швидко стає неприйнятним для великих динамічних систем. Ліс зв’язків був розроблений саме для того, щоб уникнути цього: він гарантує, що запити на зв'язування, розрізання та шляхи виконуються з амортизованою складністю O(log n), незалежно від того, як переструктурується ліс, завдяки розумному обмеженню загального обсягу роботи, виконаної серією операцій, а не обмеженню кожної окремої операції ізольовано.”]} p1:

paragraphs_2

Розкладання за відданими шляхами

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

Операція Доступу та З’єднання”, “paragraphs”: [

Більшість операцій з дерев із посиланнями та зрізами будуються на основі одного базового примітиву під назвою «доступ». Придано точку доступу, вона йде від даної точки до кореня її представленого дерева, і в процесі цього кожний край на цьому шляху перетворюється на улюблений край, по суті просуваючи весь шлях від точки до кореня як єдиний улюблений шлях. Це робиться шляхом повторного розгортання точки доступу до кореня її власного допоміжного дерева сплайну, а потім слідування за пунктирною лінією до батьківського шляху, розгортаючи там також і його, і перемикаючи, який з дітей раніше був улюбленим, щоб шлях, щойно пройдений, став улюбленим. Цей процес часто називають «з’єднанням»: на кожному кроці допоміжне дерево сплайну поточної траєкторії з’єднується з допоміжною траєкторією сплайну наступної траєкторії вгору, використовуючи операцію сплайну для повторного приєднання та ребалансування. Після завершення доступу, отримана точка доступу є найглибшою точкою в одному дереві сплайн, яке охоплює весь шлях від кореня до точки, і вона була розгорнута до кореня цього допоміжного дерева, забезпечуючи безпосередній доступ до неї та, як наслідок, інформацію про весь шлях. Оскільки дерева сплайн гарантують амортизоване логарифмічне час на операцію за допомогою добре відомого аргументу потенційної функції, і оскільки кількість відмінних улюблених шляхів, перетнутих під час будь-якого доступу, сама по собі обмежена логарифмічно в амортизованому сенсі, вся операція доступу виконується за амортизоване O(log n) часу. Кожна інша операція з дерев із посиланнями та зрізами, включаючи об’єднання, розрізання, пошук кореня та запити агрегації шляху, такі як мінімальна вартість краю, виражаються як невелике число константних доступу плюс O(1) додаткове маніпулювання покажчиками, що пояснює, чому вся структура успадкувала той самий логарифмічний ліміт.”

Практичне застосування запитів Link, Cut та Path

Маючи доступ як основну функцію, інші операції стають короткими та елегантними. Щоб зв’язати два дерева, зробивши вузол u дитиною вузла v, спочатку отримуємо доступ до u, щоб привести його до кореня його представленого дерева без переважного батька, а потім прикріплюємо його як нового переважного дитину під вузлом v після отримання доступу до v. Щоб обірвати ребро над вузлом u, отримуємо доступ до u, що призводить до того, що весь шлях від u до кореня дерева його дерева стає єдиним спливчастим деревом з u в найглибшій позиції; оскільки порядок спливчого дерева відповідає глибині, ліве піддерево u в цьому спливчому дереві відповідає всім належним предкам u, тому обрізання є просто справою від’єднання цього лівого піддерева, операція з покажчиками O(1) після того, як спливне дерево організовано. Щоб відповісти на запит шляху, наприклад, мінімальна вага ребра між двома вузлами, ми зазвичай отримуємо доступ до одного вузла, щоб зробити його коренем усього лісу (техніка часто називається make-root або evert, досягнута неактивною прапорцем перевертання орієнтації), потім отримуємо доступ до другого вузла, і щойно утворене спливне дерево охоплює точно шлях між ними, дозволяючи нам прочитати агрегатне значення, яке підтримується поступово в кожному вузлі спливного дерева, подібно до того, як сегментне дерево підтримує агрегати діапазонів. Ці будівельні блоки роблять Link-Cut Trees інструментом вибору для алгоритмів, таких як підтримка динамічного мінімального спледняного лісу при вставках і видаленнях ребер, пришвидшення алгоритмів потоку мережі, таких як покращення деревних динамічних алгоритмів Дініка, та підтримка повністю динамічних запитів з’єднання, де додаються та видаляються ребра протягом тривалого ряду операцій.

Контраст із статичними деревами

Значення структури типу ‘зв’язок-різа’ стає очевидним, коли порівнюють її зі статичною структурою, що використовується для представлення того ж динамічного навантаження. Статичне дерево зазвичай будується один раз, наприклад, з використанням попередньо обчислених таблиць предків для бінарного підйому, Ейлера турну для запитів про найнижчого спільного предка або розкладу ‘важкий-світлий’, відображеного на сегментному дереві. Усі ці методи чудово працюють, коли форма дерева ніколи не змінюється, забезпечуючи швидкі запити після одноразового часу попередньої обробки. Але як тільки потрібно вирізати гілку глибоко всередині дерева або додати новий піддерево, ця попередньо обчислена інформація стає застарілою. Ейлер тур повинен бути побудований знову, таблиці предків повинні бути перераховані для потенційно кожного нащадка зміненого піддерева, а розклад ‘важкий-світлий’ може потребувати повного перепризначення ланцюгів, що може зайняти O(n) часу для одного оновлення в найгіршому випадку. Якщо оновлення часті та чергуються з запитами, як це відбувається в задачах динамічної зв'язності або підтримки мінімального сплету графів онлайн, цей статичний підхід деградує до неприйнятного загального часу виконання протягом тривалого ряду операцій. ‘Зв’язок-різа’ повністю обходить цю проблему, ніколи не зобов’язуючись фіксованим розкладом: її переважні шляхи дозволяється зміщувати з кожним доступом, а вартість цього зміщення оплачується за допомогою заамортизованого аналізу підлеглого сplay-дерева, щоб навіть найгірший випадковий послідовність зв’язків, розрізів та запитів все ще становила лише O(m log n) часу для m операцій на графі з n вершинами. Це основний компроміс, який має продемонструвати лабораторія: статична структура купує простоту та швидкість запитів лише тоді, коли нічого не змінюється, а ‘зв’язок-різа’ купує стійкість до постійного переструктурування за рахунок більш складної внутрішньої репрезентації.

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

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

Усе, що вище, працює прямо у вашому браузері — відкрийте Link-Cut Tree і змінюйте параметри під час роботи. Нічого не встановлюється, нічого не завантажується на сервер, уся модель живе в одній вкладці.