1632
правки
Изменения
м
rollbackEdits.php mass rollback
<br>
Представим дерево в виде последовательности вершин, посещеннных посещенных в порядке эйлерова обхода, начиная с вершины <tex>a</tex>.
[[Файл:Tour1.png|thumb|320px|center]]
*Выберем любое вхождение вершины <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>.
===Проверка на связность===
Для того, чтобы проверить, лежат ли 2 две вершины в одном дереве, достаточно подняться от вхождения каждой вершины в эйлеров обход (ссылку на которое мы храним) до корня дерева поиска, хранящего этот элеров эйлеров обход.
==Способы реализации структуры==
===Декартово дерево по неявному ключу===
Также, можем хранить последовательности вершин эйлерова обхода в [[Декартово_дерево_по_неявному_ключу|декартовом дереве по неявному ключу]]. Глубина декартового дерева, построенного на массиве из <tex>n </tex> вершин, будет поддерживаться равной <tex>O(\log n)</tex>.
Операции объединения и разделения так же также выполняются за <tex>O(\log n)</tex>.
==См. также==
