CODEWITHSUNDEEP
javac++algorithmdata-structures
outlaw
outlaw

Reputation: 1193

Disjoint set data structure supporting deletion

Assume that we have a set of n disjoint nodes {node1,node1,...,noden}

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

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

  2. IsConnected(x,y): returns true if nodex and nodey are connected directly or indirectly, i.e nodex and nodey are in the the same connected component.

  3. Un-union(x,y): remove the edge between nodex and nodey 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.

Upvotes: 12

Views: 9212

Answers (2)

Evgeny Kluev
Evgeny Kluev

Reputation: 24677

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(log2 N).

Upvotes: 12

Eran
Eran

Reputation: 729

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.

Upvotes: 7

Related Questions