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

Введение

Динамические деревья (англ.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.

Операции

Rerooting a Tour

link(u ,v)

cut(u ,v)

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

Linked Lists

Balanced Trees

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

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

Про link-cut trees