1632
правки
Изменения
м
Нужно поддерживать следующие операции * '''<tex>\mathrm{linkДля решения поставленной задачи будем представлять дерево в виде его [[Эйлеровость графов|эйлерова графа]], а затем будем работать с [[Эйлеровость графов|эйлеровым обходом]] (u, w)}</tex>англ.''Euler tour tree' {{---}} добавить ребро (u, w) (при условии, что вершины u w принадлежат разным деревьям)* '''<tex>\mathrm{cut(u, w)}этого графа. Это позволит выполнять указанные запросы за </tex>''' {{---}} разрезать ребро O(u, w) (при условии, что ребро (u, w) принадлежит дереву),* '''<tex>\mathrm{isConnected(u, wlog n)}</tex>''' {{---}} принадлежат ли вершины u и w одной компоненте связности.
''' Euler tour tree''' - The data structure we'll develop can perform these operations time O(log n) each.==Представление деревьев в виде эйлерова графа==
==[[Файл:Tree.png|300px|thumb|left|Пример дерева]][[Файл:Euler Tours on Trees==graph.png|300px|thumb|right|Соответствующий эйлеров граф]]
Euler ToursДля представления [[Дерево, эквивалентные определения|дерева]] в виде [[Эйлеровость графов|эйлерового графа]] заменим каждое ребро <tex>\{u, v\} \</tex> дерева на два ребра <tex>(u, v)</tex> и <tex>(v, u)</tex>.
In a graph G, an Euler tour is a path through the graph that visits every edge exactly onceПолучившийся [[Основные определения теории графов|ориентированный граф]] будет эйлеровым согласно [[Эйлеровость графов|критерию]].<br><br>Mathematically formulates the “trace this figure without picking up your pencil or redrawing any lines” puzzles.<br><br><br><br><br><br>
===Rerooting a Tour===Для добавления ребра <tex>(c, g)</tex>:*Выберем любое вхождение вершины <tex>c</tex> в эйлеров обход дерева <tex>T1</tex>.*Разрежем эйлеров обход <tex>T1</tex> на две части:*: <tex>A1</tex> {{---}} часть обхода до выбранного вхождения вершины <tex>c</tex>, включая ее.*: <tex>A2</tex> {{---}} часть обхода после выбранного вхождения вершины <tex>c</tex>, включая ее.*Аналогично, выберем любое вхождение вершины <tex>g</tex> в эйлеров обход дерева <tex>T2</tex> и разрежем его на две части <tex>B1</tex> и <tex>B2</tex>.*Соберем результирующий эйлеров обход в порядке <tex>A1, B2, B1</tex> (без первой повторяющейся вершины), <tex>A2</tex>.
===linkЧтобы быстро находить место, где разрезать эйлеровы обходы деревьев <tex>T1</tex> и <tex>T2</tex>, будем хранить эйлеровы обходы в двоичных деревьях поиска. Ключом вершины для построения дерева поиска будет время посещения этой вершины эйлеровым обходом.Для каждой вершины дерева <tex>(T1, T2)</tex> будем хранить указатель на вершину в дереве поиска, которая соответствует вхождению вершины дерева в эйлеров обход. Тогда за <tex>O(u 1)</tex> переходим от вершины дерева к вершине дерева поиска,vпо которой за <tex>O(\log n)===</tex> можно будет разделить дерево поиска на две части.
===cut(u ,v)===[[Файл:Link22.png |thumb|400px|center|Рис.1a Исходный лес <br>Рис.1b Эйлеровы обходы деревьев<br> Рис.1с Двоичные деревья поиска для хранения эйлеровых обходов <br> Рис.1d Результирующий эйлеров обход]]
==Реализация структуры==Для удаления ребра <tex>(g, j)</tex>:*Найдем в эйлеровом обходе дерева <tex>T</tex> две пары посещений концов удаляемого ребра <tex>g,j</tex> и <tex>j,g</tex>, которые соответствуют прохождениям по ребру <tex>(g, j)</tex> в дереве <tex>T</tex>.*Разрежем эйлеров обход дерева по этим парам на три части: <tex>A1, A2, A3</tex>.*Соединив <tex>A1</tex> и <tex>A3</tex> (без повторяющейся первой вершины), получим эйлеров обход первого дерева, а <tex>A2</tex> дает эйлеров обход второго дерева.
===Linked Lists===Чтобы быстро находить места в эйлеровом обходе, которые соответствуют прохождению удаляемого ребра в дереве, будем для каждого ребра в дереве хранить ссылку на те места эйлерова обхода, где последовательно посещаем концы удаляемого ребра.Так, для ребра <tex>(g, j)</tex> храним ссылки на узлы дерева поиска, соответствующие парам посещений концов этого ребра.
===Balanced Trees===[[Файл:Link23.png |thumb|400px|center|Рис.1a Исходное дерево <br>Рис.1b Эйлеров обход исходного дерева<br> Рис.1с Двоичное дерево поиска для хранения эйлерового обхода <br> Рис.1d Эйлеровы обходы получившихся деревьев]]
Сравнительная табличка==Способы реализации структуры==
rollbackEdits.php mass rollback
==ВведениеЗадача о динамической связности=={{Задача|definition = Для динамически изменяющегося дерева выполнить следующие запросы:* '''Динамические деревья<tex>\mathrm{link(u, w)}</tex>''' {{---}} добавить ребро <tex>(англ.u, w)</tex> (при условии, что вершины <tex>u</tex> и <tex>w</tex> принадлежат разным деревьям),* '''<tex>\mathrm{cut(u, w)}</tex>'dynamic tree''{{---}} разрезать ребро <tex>(u, w) используются в двух областях:........</tex> (при условии, что ребро <tex>(u, w)</tex> принадлежит дереву),* '''<tex>\mathrm{isConnected(u, w)}</tex>''' {{---}} определить принадлежат ли вершины <tex>u</tex> и <tex>w</tex> одной компоненте связности.}}
Представим дерево в виде последовательности вершин, посещенных в порядке эйлерова обхода, начиная с вершины <tex>a</tex>.[[Файл:Simple graphTour1.png |400pxthumb|thumb320px|center|Пример ]]
==Properties of Euler ToursОперации c эйлеровыми обходами==
==Операции=Добавление ребра===
===Разрезание ребра===
===Проверка на связность===
Для того, чтобы проверить, лежат ли две вершины в одном дереве, достаточно подняться от вхождения каждой вершины в эйлеров обход (ссылку на которое мы храним) до корня дерева поиска, хранящего этот эйлеров обход.
==Похожие структуры=Сбалансированное дерево поиска=== Будем хранить последовательность вершин эйлерова обхода в виде сбалансированного двоичного дерева поиска, например, в виде [[Красно-черное дерево|красно-черного дерева]]. При построении дерева ключом вершины будет время посещения этой вершины эйлеровым обходом. Операции объединения и разделения красно-черных деревьев выполняется за <tex>O(\log n)</tex><ref>[http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.109.4875&rep=rep1&type=pdf Ron Wein {{---}} Efficient Implementation of Red-Black Trees.]</ref>. ===Декартово дерево по неявному ключу=== Также, можем хранить последовательности вершин эйлерова обхода в [[Декартово_дерево_по_неявному_ключу|декартовом дереве по неявному ключу]]. Глубина декартового дерева, построенного на массиве из <tex>n</tex> вершин, будет поддерживаться равной <tex>O(\log n)</tex>. Операции объединения и разделения также выполняются за <tex>O(\log n)</tex>. ==См. также==* [[Link-Cut Tree]] == Примечания ==<references/> ==Источники информации==Про link* [https://en.wikipedia.org/wiki/Euler_tour_technique Wikipedia {{---}} Euler tour technique]* [http://courses.csail.mit.edu/6.851/spring07/scribe/lec05.pdf Advanced Data Structures {{---}} Euler tour trees]* [http://codeforces.com/blog/entry/18369?mobile=true&locale=en CodeForces {{---cut }} On Euler tour trees]* [http://logic.pdmi.ras.ru/csclub/node/2819 Лекториум{{---}} Лекция Павла Маврина об эйлеровых обходах] [[Категория: Алгоритмы и структуры данных]][[Категория: Обходы графов]][[Категория: Эйлеровы графы]]
