Unbound set data structure that supports deletion

Question

Suppose we have a set of n disjoint nodes {node ₁ , node ₁ , ..., node _nsub>}

What is the fastest data structure and algorithm for the following three operations:

• Union (x, y): add an undirected edge between node _x and node _y , there can be at most one edge between two nodes.

• IsConnected (x, y): returns true if node _x and node _y are connected directly or indirectly, i.e. node _x and node _y are in the same connection component.

• Un-union (x, y): remove the border between node _x and node _y , if it exists.

Disjoint-set is an ideal data structure for the first two operations, but it cannot support the third operation directly. Which alternative?

If we simulate a process, the first and third operations can be implemented in O (1), but the 2nd operation is O (n), so I would like to see if all three operations can be done in O (logn) time or less.

Answer 1

Link / cut tree can perform these 3 operations in O (log N).

You can read about the Link / cut tree and related data structures in this book: "A Guide to Data Structures and Applications" (chapter 35).

The link / cut tree does not allow you to add a border between nodes that are already (indirectly) connected. If you need the operation "Union (x, y)", the task becomes more complex, and you can solve it as a problem of dynamic connectivity in undirected graphs. (See Chapter 36.4 in the same book or this pdf ). In this case, the complexity of the insertion / deletion increases to O (log ² N).

Answer 2

Kaplan, Shafrir and Tarjan offer a common technique for adding deletion to union-find data structures by incrementally rebuilding and displaying deletion O (t_f (n) + t_i (n)), which are the costs of finding and inserting a node, respectively. The general idea is to save the number of deleted items in each set and rebuild the set when that number reaches a certain threshold.

Alstrup, Gørtz, Rauhe, Thorup, and Zwick show how to implement permanent deletion by noting which elements in the tree are busy and which are empty and “tidy up” the tree after delete operations.