635
правок
Изменения
→Связные списки
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?
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===
