Disjoint set data structure supporting deletion

Question

Assume that we have a set of n disjoint nodes {node₁,node₁,...,node_n}

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

1. Union(x,y): add an un-directed edge between node_x and node_y, there can be at most one edge between two nodes.

2. 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 the same connected component.

3. Un-union(x,y): remove the edge between node_x and node_y if it exists.

Disjoint-set is a perfect data structure for the first two operations, but it cannot support the 3rd operation directly. What is the alternative?

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

Answer 1

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

You can read about Link/cut tree and related data structures in this book: "Handbook of Data Structures and Applications" (Chapter 35).

Link/cut tree does not allow adding an edge between nodes, that are already (indirectly) connected. If you need "Union(x,y)" operation to support this, the problem becomes more complicated, and you can solve it as dynamic connectivity problem in undirected graphs. (See chapter 36.4 in the same book or this pdf). In this case insertion/deletion complexity increases to O(log² N).

Answer 2

Kaplan, Shafrir and Tarjan propose a general technique to add deletion to union-find data structures by incremental rebuilding and show deletion takes O(t_f(n) + t_i(n)) which are the costs for finding and inserting a node, respectively. The general idea is keeping the number of deleted items in each set and rebuilding the set when this number reaches a certain threshold.

Alstrup ,Gørtz , Rauhe, Thorup and Zwick show how to implement deletions in constant time by noting which elements in a tree are occupied and which are vacant and "tidying up" the tree after delete operations.