Деревья Эйлерова обхода

Введение

Динамические деревья (англ.dynamic tree) используются в двух областях:.........

Нужно поддерживать следующие операции

• [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 - The data structure we'll develop can perform these operations time O(log n) each.

Euler Tours on Trees

Euler Tours

In a graph G, an Euler tour is a path through the graph that visits every edge exactly once.
Mathematically formulates the “trace this figure without picking up your pencil or redrawing any lines” puzzles.

Пример

Euler Tours on Trees

In general, trees do not have Euler tours.

Пример

Technique: replace each edge {u, v} with two edges (u, v) and (v, u).
Resulting graph has an Euler tour.

High-level idea: Instead of storing the trees in the forest, store their Euler tours. Each edge insertion or deletion translates into a set of manipulations on the Euler tours of the trees in the forest.
Checking whether two nodes are connected can be done by checking if they're in the same Euler tour.

Properties of Euler Tours

The sequence of nodes visited in an Euler tour of a tree is closely connected to the structure of the tree.

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

Balanced Trees

Сравнительная табличка

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

Про link-cut trees