Деревья Эйлерова обхода — различия между версиями
Sokolova (обсуждение | вклад) |
Sokolova (обсуждение | вклад) |
||
| Строка 6: | Строка 6: | ||
* '''<tex>\mathrm{cut(u, w)}</tex>''' {{---}} разрезать ребро (u, w) (при условии, что ребро (u, w) принадлежит дереву), | * '''<tex>\mathrm{cut(u, w)}</tex>''' {{---}} разрезать ребро (u, w) (при условии, что ребро (u, w) принадлежит дереву), | ||
* '''<tex>\mathrm{isConnected(u, w)}</tex>''' {{---}} принадлежат ли вершины u и w одной компоненте связности. | * '''<tex>\mathrm{isConnected(u, w)}</tex>''' {{---}} принадлежат ли вершины u и w одной компоненте связности. | ||
| + | |||
| + | ''' Euler tour tree''' - The data structure we'll develop can perform these operations time O(log n) each. | ||
| + | |||
| + | ==Euler Tours on Trees== | ||
Версия 19:42, 28 ноября 2016
Введение
Динамические деревья (англ.dynamic tree) используются в двух областях:.........
Нужно поддерживать следующие операции
- — добавить ребро (u, w) (при условии, что вершины u w принадлежат разным деревьям)
- — разрезать ребро (u, w) (при условии, что ребро (u, w) принадлежит дереву),
- — принадлежат ли вершины u и w одной компоненте связности.
Euler tour tree - The data structure we'll develop can perform these operations time O(log n) each.
