635
правок
Изменения
→Реализация структуры
==Реализация структуры==
Goal: Implement link, cut, and is-connected as efficiently as possible.
By representing trees via their Euler tours, can implement link and cut so that only O(1) joins and splits are necessary per operation.
Questions to answer:<br>
How do we efficiently implement these joins and splits?<br>
Once we have the tours, how do we answer connectivity queries?
Implementing the Structure
The operations we have seen require us to be able to efficiently do the following:<br>
Identify the first and last copy of a node in a sequence.<br>
Split a sequence at those positions.<br>
Concatenate sequences.<br>
Add a new copy of a node to a sequence.<br>
Delete a duplicate copy of a node from a sequence.<br>
How do we do this efficiently?
===Linked Lists===
