Each split or concatenate takes time O(1). Каждое разбиение и соединение последовательностей требует О(1) времени.<br>The first and last copy of a node can be identified in time O(1).Определение первого и последнего вхождения вершины в последовательность происходит за О(1).<br>A new copy of a node can be appended to the end of the sequence in time O(1).Новая копия вершины может быть добавлена в конец последовательности за О(1).<br>A redundant copy of a node can be deleted in time O(1).Лишняя копия вершины может быть удалена за О(1).<br>Everything sounds great!<br>Question: How do you test for connectivity?
Euler tours give a simple, flexible encoding of tree structuresДля каждой вершины будем хранить указатели на первое и последнее вхождение вершины в последовательность.<br>Using doubly-linked lists, concatenation and splits take time OТогда возможно определять первое и последнее вхождение вершины за О(1) each, but testing connectivity takes time Θ(n) in the worst-case.<br>Can we do better?Используя двойные связные Однако,используя двусвязные списки добавление и разрезание ребра может быть проведено за время О(1), но определение принадлежности вершин одной компоненте связности занимает ΘО(n) в худшем случае.
===Balanced Trees===
