Деревья Эйлерова обхода — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Разрезание ребра)
(Декартово дерево по неявному ключу)
 
(не показано 39 промежуточных версий 5 участников)
Строка 26: Строка 26:
 
<br>
 
<br>
  
Представим дерево с корнем в вершине <tex>a</tex> в виде последовательности вершин, посещеннных в порядке эйлерова обхода.
+
Представим дерево в виде последовательности вершин, посещенных в порядке эйлерова обхода, начиная с вершины <tex>a</tex>.
 
[[Файл:Tour1.png|thumb|320px|center]]
 
[[Файл:Tour1.png|thumb|320px|center]]
 
{{Утверждение
 
|statement=Последовательность вершин между первым и последним вхождениями вершины <tex>h</tex> в эйлеров обход дерева, представляет эйлеров обход поддерва с корнем в <tex>h</tex>.
 
|proof=Действительно, при обходе дерева последний раз выйдем из вершины, только после посещения всех вершин ее поддерева.
 
[[Файл:Tour2.png|thumb|320px|center]]
 
}}
 
  
 
==Операции c эйлеровыми обходами==
 
==Операции c эйлеровыми обходами==
Представление деревьев в виде их эйлеровых обходов позволяет свести задачу о динамической связности к следующим операциям с последовательностями вершин:
 
  
 
===Добавление ребра===
 
===Добавление ребра===
  
[[Файл:Link11.png |thumb|400px|center]]
+
Для добавления ребра <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>.
  
Для добавления ребра (c, g):
+
Чтобы быстро находить место, где разрезать эйлеровы обходы деревьев <tex>T1</tex> и <tex>T2</tex>, будем хранить эйлеровы обходы в двоичных деревьях поиска.  
*Выберем любое вхождение вершины c в эйлеров обход T1.
+
Ключом вершины для построения дерева поиска будет время посещения этой вершины эйлеровым обходом.
*Разрежем эйлеров обход T1 на 2 части:
+
Для каждой вершины дерева <tex>(T1, T2)</tex> будем хранить указатель на вершину в дереве поиска, которая соответствует вхождению вершины дерева в эйлеров обход.
*: A1 - часть обхода до выбранного вхождения вершины c.
+
Тогда за <tex>O(1)</tex> переходим от вершины дерева к вершине дерева поиска, по которой за <tex>O(\log n)</tex> можно будет разделить дерево поиска на две части.
*: A2 - часть обхода после выбранного вхождения вершины c.
 
*Аналогично, выберем любое вхождение вершины g в эйлеров обход T2 и разрежем его на 2 части B1 и B2.
 
*Соберем результирующий эйлеров обход в порядке A1 B2 B1 A2.
 
  
Чтобы быстро находить место, где разрезать эйлеровы обходы деревьев T1 и T2, будем хранить эйлеровы обходы в двоичных деревьях поиска.
+
[[Файл:Link22.png |thumb|400px|center|Рис.1a Исходный лес <br>Рис.1b Эйлеровы обходы деревьев<br> Рис.1с Двоичные деревья поиска для хранения эйлеровых обходов <br> Рис.1d Результирующий эйлеров обход]]
Ключом вершины, для построения дерева поиска, будет время посещения этой вершины эйлеровым обходом.
 
Для каждой вершины дерева (T1, T2) будем хранить указатель на вершину в дереве поиска, которая соответствует вхождению вершины дерева в эйлеров обход.
 
Тогда за O(1) переходим от вершины дерева к вершине дерева поиска, по которой за O(log n) можно будет разделить дерево поиска на 2 части.
 
  
 
===Разрезание ребра===
 
===Разрезание ребра===
[[Файл:Cut1.png|thumb|350px|center]]
 
  
Для удаления ребра <tex>\{g, j\} \</tex>:
+
Для удаления ребра <tex>(g, j)</tex>:
*Найдем в эйлеровом обходе дерева T две пары посещений концов удаляемого ребра gj и jg, которые соответствуют прохождениям по ребру (g, j) в T.
+
*Найдем в эйлеровом обходе дерева <tex>T</tex> две пары посещений концов удаляемого ребра <tex>g,j</tex> и <tex>j,g</tex>, которые соответствуют прохождениям по ребру <tex>(g, j)</tex> в дереве <tex>T</tex>.
*Разрежем эйлеров обход дерева по этим парам на 3 части: A1, A2, A3
+
*Разрежем эйлеров обход дерева по этим парам на три части: <tex>A1, A2, A3</tex>.
*Соберем результирующий обход в порядке A1, A3, A2
+
*Соединив <tex>A1</tex> и <tex>A3</tex> (без повторяющейся первой вершины), получим эйлеров обход первого дерева, а <tex>A2</tex> дает эйлеров обход второго дерева.
  
 
Чтобы быстро находить места в эйлеровом обходе, которые соответствуют прохождению удаляемого ребра в дереве, будем для каждого ребра в дереве хранить ссылку на те места эйлерова обхода, где последовательно посещаем концы удаляемого ребра.
 
Чтобы быстро находить места в эйлеровом обходе, которые соответствуют прохождению удаляемого ребра в дереве, будем для каждого ребра в дереве хранить ссылку на те места эйлерова обхода, где последовательно посещаем концы удаляемого ребра.
Так, для ребра (g, j) храним ссылки на узлы дерева поиска, соответствующие парам посещений концов этого ребра.
+
Так, для ребра <tex>(g, j)</tex> храним ссылки на узлы дерева поиска, соответствующие парам посещений концов этого ребра.
 +
 
 +
[[Файл:Link23.png |thumb|400px|center|Рис.1a Исходное дерево <br>Рис.1b Эйлеров обход исходного дерева<br> Рис.1с Двоичное дерево поиска для хранения эйлерового обхода <br> Рис.1d Эйлеровы обходы получившихся деревьев]]
 +
 
 +
===Проверка на связность===
 +
Для того, чтобы проверить, лежат ли две вершины в одном дереве, достаточно подняться от вхождения каждой вершины в эйлеров обход (ссылку на которое мы храним) до корня дерева поиска, хранящего этот эйлеров обход.
  
==Реализация структуры==
+
==Способы реализации структуры==
  
Представим последовательность вершин эйлерова обхода в виде сбалансированного двоичного дерева. Будем использовать [[Красно-черное дерево|красно-черное дерево]].
+
===Сбалансированное дерево поиска===
  
[[Файл:Balanced tree.png |center]]
+
Будем хранить последовательность вершин эйлерова обхода в виде сбалансированного двоичного дерева поиска, например, в виде [[Красно-черное дерево|красно-черного дерева]]. При построении дерева ключом вершины будет время посещения этой вершины эйлеровым обходом.
  
Объединение и разделение красно-черных деревьев выполняется за <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>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>O(1)</tex>.
+
===Декартово дерево по неявному ключу===
  
Запрос о принадлежности вершин к одной компоненте связности выполняется за <tex>O(\log n)</tex> проверкой лежат ли эти вершины в одном дереве.
+
Также, можем хранить последовательности вершин эйлерова обхода в [[Декартово_дерево_по_неявному_ключу|декартовом дереве по неявному ключу]]. Глубина декартового дерева, построенного на массиве из <tex>n</tex> вершин, будет поддерживаться равной <tex>O(\log n)</tex>.  
  
[[Файл:Balanced tree1.png |center]]
+
Операции объединения и разделения также выполняются за <tex>O(\log n)</tex>.
  
 
==См. также==
 
==См. также==
Строка 90: Строка 87:
 
* [http://courses.csail.mit.edu/6.851/spring07/scribe/lec05.pdf Advanced Data Structures {{---}} Euler tour trees]
 
* [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 {{---}} On Euler tour trees]
 
* [http://codeforces.com/blog/entry/18369?mobile=true&locale=en CodeForces {{---}} On Euler tour trees]
 +
* [http://logic.pdmi.ras.ru/csclub/node/2819 Лекториум{{---}} Лекция Павла Маврина об эйлеровых обходах]
  
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Обходы графов]]
 
[[Категория: Обходы графов]]
 
[[Категория: Эйлеровы графы]]
 
[[Категория: Эйлеровы графы]]

Текущая версия на 10:27, 26 октября 2019

Задача о динамической связности[править]

Задача:
Для динамически изменяющегося дерева выполнить следующие запросы:
  • [math]\mathrm{link(u, w)}[/math] — добавить ребро [math](u, w)[/math] (при условии, что вершины [math]u[/math] и [math]w[/math] принадлежат разным деревьям),
  • [math]\mathrm{cut(u, w)}[/math] — разрезать ребро [math](u, w)[/math] (при условии, что ребро [math](u, w)[/math] принадлежит дереву),
  • [math]\mathrm{isConnected(u, w)}[/math] — определить принадлежат ли вершины [math]u[/math] и [math]w[/math] одной компоненте связности.


Для решения поставленной задачи будем представлять дерево в виде его эйлерова графа, а затем будем работать с эйлеровым обходом (англ.Euler tour tree) этого графа. Это позволит выполнять указанные запросы за [math]O(\log n)[/math].

Представление деревьев в виде эйлерова графа[править]

Пример дерева
Соответствующий эйлеров граф

Для представления дерева в виде эйлерового графа заменим каждое ребро [math]\{u, v\} \[/math] дерева на два ребра [math](u, v)[/math] и [math](v, u)[/math].

Получившийся ориентированный граф будет эйлеровым согласно критерию.







Представим дерево в виде последовательности вершин, посещенных в порядке эйлерова обхода, начиная с вершины [math]a[/math].

Tour1.png

Операции c эйлеровыми обходами[править]

Добавление ребра[править]

Для добавления ребра [math](c, g)[/math]:

  • Выберем любое вхождение вершины [math]c[/math] в эйлеров обход дерева [math]T1[/math].
  • Разрежем эйлеров обход [math]T1[/math] на две части:
    [math]A1[/math] — часть обхода до выбранного вхождения вершины [math]c[/math], включая ее.
    [math]A2[/math] — часть обхода после выбранного вхождения вершины [math]c[/math], включая ее.
  • Аналогично, выберем любое вхождение вершины [math]g[/math] в эйлеров обход дерева [math]T2[/math] и разрежем его на две части [math]B1[/math] и [math]B2[/math].
  • Соберем результирующий эйлеров обход в порядке [math]A1, B2, B1[/math] (без первой повторяющейся вершины), [math]A2[/math].

Чтобы быстро находить место, где разрезать эйлеровы обходы деревьев [math]T1[/math] и [math]T2[/math], будем хранить эйлеровы обходы в двоичных деревьях поиска. Ключом вершины для построения дерева поиска будет время посещения этой вершины эйлеровым обходом. Для каждой вершины дерева [math](T1, T2)[/math] будем хранить указатель на вершину в дереве поиска, которая соответствует вхождению вершины дерева в эйлеров обход. Тогда за [math]O(1)[/math] переходим от вершины дерева к вершине дерева поиска, по которой за [math]O(\log n)[/math] можно будет разделить дерево поиска на две части.

Рис.1a Исходный лес
Рис.1b Эйлеровы обходы деревьев
Рис.1с Двоичные деревья поиска для хранения эйлеровых обходов
Рис.1d Результирующий эйлеров обход

Разрезание ребра[править]

Для удаления ребра [math](g, j)[/math]:

  • Найдем в эйлеровом обходе дерева [math]T[/math] две пары посещений концов удаляемого ребра [math]g,j[/math] и [math]j,g[/math], которые соответствуют прохождениям по ребру [math](g, j)[/math] в дереве [math]T[/math].
  • Разрежем эйлеров обход дерева по этим парам на три части: [math]A1, A2, A3[/math].
  • Соединив [math]A1[/math] и [math]A3[/math] (без повторяющейся первой вершины), получим эйлеров обход первого дерева, а [math]A2[/math] дает эйлеров обход второго дерева.

Чтобы быстро находить места в эйлеровом обходе, которые соответствуют прохождению удаляемого ребра в дереве, будем для каждого ребра в дереве хранить ссылку на те места эйлерова обхода, где последовательно посещаем концы удаляемого ребра. Так, для ребра [math](g, j)[/math] храним ссылки на узлы дерева поиска, соответствующие парам посещений концов этого ребра.

Рис.1a Исходное дерево
Рис.1b Эйлеров обход исходного дерева
Рис.1с Двоичное дерево поиска для хранения эйлерового обхода
Рис.1d Эйлеровы обходы получившихся деревьев

Проверка на связность[править]

Для того, чтобы проверить, лежат ли две вершины в одном дереве, достаточно подняться от вхождения каждой вершины в эйлеров обход (ссылку на которое мы храним) до корня дерева поиска, хранящего этот эйлеров обход.

Способы реализации структуры[править]

Сбалансированное дерево поиска[править]

Будем хранить последовательность вершин эйлерова обхода в виде сбалансированного двоичного дерева поиска, например, в виде красно-черного дерева. При построении дерева ключом вершины будет время посещения этой вершины эйлеровым обходом.

Операции объединения и разделения красно-черных деревьев выполняется за [math]O(\log n)[/math][1].

Декартово дерево по неявному ключу[править]

Также, можем хранить последовательности вершин эйлерова обхода в декартовом дереве по неявному ключу. Глубина декартового дерева, построенного на массиве из [math]n[/math] вершин, будет поддерживаться равной [math]O(\log n)[/math].

Операции объединения и разделения также выполняются за [math]O(\log n)[/math].

См. также[править]

Примечания[править]

Источники информации[править]