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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Balanced Trees)
(Balanced Trees)
Строка 100: Строка 100:
  
 
===Balanced Trees===
 
===Balanced Trees===
 +
[[Файл:Balanced tree.png |center|Пример ]]
  
 +
Представим последовательность вершин эйлерова обхода в виде сбалансированного двоичного дерева. Будем использовать красно-черное дерево.
  
 +
Объединение и разделение красно-черных деревьев выполняется за O(log n).
  
These are not binary search trees. We're using the shape of a red/black tree to ensure balance.
+
Для каждой вершины храним указатели на её первое и последнее вхождение в последовательность. Значит, имеем доступ к ним за <tex>О(1)</tex>.
 
 
[[Файл:Balanced tree.png |center|Пример ]]
 
 
 
Observation 1: Can still store pointers to the first and last occurrence of each tree node.
 
 
 
Observation 2: If nodes store pointers to their parents, can answer is-connected(u, v) in time O(log n) by seeing if u and v are in the same tree.
 
  
Observation 3: Red/black trees can be split and joined in time O(log n) each.
+
Запрос о принадлежности вершин к одной компоненте связности выполняется за O(log n) проверкой лежат ли эти вершины в одном дереве.
  
 
[[Файл:Balanced tree1.png |center|Пример ]]
 
[[Файл:Balanced tree1.png |center|Пример ]]
 
The data structure:<br>
 
Represent each tree as an Euler tour.<br>
 
Store those sequences as balanced binary trees.<br>
 
Each node in the original forest stores a pointer to its first and last occurrence.<br>
 
Each node in the balanced trees stores a pointer to its parent.<br>
 
link, cut, and is-connected queries take time only O(log n) each.
 
 
 
Сравнительная табличка
 
  
 
==Похожие структуры==
 
==Похожие структуры==
 
Про link-cut trees
 
Про link-cut trees

Версия 17:12, 4 декабря 2016

Введение

Для решения задачи о динамической связности (англ.dynamic connectivity problem) требуется выполнение следующих операций:

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

Дерево эйлерова обхода (англ.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

При этом последовательность вершин между первым и последним вхождением вершины [math]h[/math] дает эйлеров обход поддерева с корнем [math]h[/math].

Tour2.png

Операции

Изменение корня дерева (переподвешивание)

Дано дерево с корнем в вершине [math]a[/math]. Требуется переподвесить его к вершине [math]h[/math].

Tour13.png

Для переподвешивания (англ. rerooting) необходимо:

  • Разбить эйлеров обход на три части [math]S1 [/math], [math]H[/math], и [math]S2 [/math], где [math]H[/math] состоит из вершин между первым и последним вхождением нового корня [math]h[/math].
  • Удалить первую вершину в [math]S1 [/math].
  • Соединить в следующем порядке: [math]H[/math], [math]S2 [/math], [math]S1 [/math].
  • Добавить [math]\{h\}[/math] в конец последовательности.

В результате получим:

Proba.png

Добавление ребра

Link11.png

Для связывания деревьев [math]T1 [/math] и [math]T2[/math], где [math]c\in T1\ [/math], а [math]g\in T2\[/math] добавлением ребра [math]\{c, g\} \[/math] необходимо:

  • Переподвесить дерево [math]T1[/math] к вершине [math]c[/math].
  • Переподвесить дерево [math]T2[/math] к вершине [math]g[/math].
  • Соединить получившиеся эйлеровы обходы.
  • Добавить [math]\{c\}[/math] в конец последовательности.
Link2.png

В результате получим:

Link3.png

Разрезание ребра

Cut1.png

Для разбиения дерева на два поддерева путем разрезания ребра [math]\{g, j\} \[/math] (если оно существует) необходимо:

  • Переподвесить дерево к вершине [math]g[/math].
  • Разделить дерево на части [math]E1, V, E2[/math], где [math]V[/math] отрезок между первым и последним вхождением вершины [math]j[/math].
  • Эйлеров обход первого поддерева образуется соединением [math]E1[/math] и [math]E2[/math], с удалением повторного [math]\{g\}[/math] в месте их соединения.
  • Эйлеров обход второго поддерева образует [math]V[/math].
Cut2.png

В результате получим:

Cut3.png

Реализация структуры

Задача:
Определить структуру данных для хранения эйлеровых обходов деревьев для наиболее эффективного выполнения указанных операций.


При представлении деревьев в виде их эйлерова обхода выполнение каждой операции [math]\mathrm{link}[/math] и [math]\mathrm{cut}[/math] сводится к [math]O(1)[/math] соединений и разбиений отрезков в последовательности вершин эйлерова обхода.

Рассмотрим следующие структуры данных для определения времени выполнения разбиения и соединения последовательностей, а также определение принадлежности вершин одной компоненте связности.

Связные списки

Linked lists.png


Каждое разбиение и соединение последовательностей требует [math]O(1)[/math].

Для каждой вершины будем хранить указатели на первое и последнее вхождение вершины в последовательность. Тогда возможно определять первое и последнее вхождение вершины за [math]O(1)[/math].

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

Balanced Trees

Пример

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

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

Для каждой вершины храним указатели на её первое и последнее вхождение в последовательность. Значит, имеем доступ к ним за [math]О(1)[/math].

Запрос о принадлежности вершин к одной компоненте связности выполняется за O(log n) проверкой лежат ли эти вершины в одном дереве.

Пример

Похожие структуры

Про link-cut trees