Java – disjoint set data structure that supports deletion

Suppose we have a set of N disjoint nodes {node1, node1,..., noden}

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

>Union (x, y): add a non directional edge between nodex and nodey. There can be at most one edge between two nodes. > Isconnected (x, y): returns true if nodex and nodey are connected directly or indirectly, that is, nodex and nodey are in the same connection component. > UN Union (x, y): delete the edge between nodex and nodey (if any)

Disjoint Set is the perfect data structure for the first two operations, but it cannot directly support the third operation What are the options?

If we simulate the process, the first and third operations can be implemented in O (1), but the second operation is O (n), so I want to see if I can run all three operations or less in O (logn) time

Solution

Link / cut tree can perform these three operations in O (log n) time

You can read about link / cut trees and related data structures in this book: "Handbook of data structures and Applications" (chapter 35)

Link / cut trees do not allow adding edges between nodes that are already (indirectly) connected If you need a "Union (x, y)" operation to support this operation, the problem will become more complex. You can solve it as a dynamic connection problem in an undirected graph (see the same book or chapter 36.4 of this PDF) In this case, the insertion / deletion complexity increases to o (log2 n)