635
правок
Изменения
→Linked Lists
===Linked Lists===
Each split or concatenate takes time O(1).<br>
The first and last copy of a node can be identified in time O(1).<br>
A new copy of a node can be appended to the end of the sequence in time O(1).<br>
A redundant copy of a node can be deleted in time O(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?
===Balanced Trees===
