Menu
Here's a breakdown on the union/find algorithm for disjoint set forests on wikipedia:
O(n))
O(log(n))
O(a(n)), effectively O(1))Implementing union by rank necessitates that each node keeps a rank field for comparison purposes. My question is, is union by rank worth this additional space? What happens if I skip union by rank and just do path compression instead? Is it good enough? What is the amortized complexity now?
A comment is made that implies that union by rank without path compression (amortized O(log(n) complexity) is sufficient for most practical application. This is correct. What I'm asking is the other way around: what if you skip union by rank and ONLY do path compression instead?
In a sense, path compression is an extra step to improve union by rank, and that's why that extra step can be omitted without disastrous consequence. But is union by rank a necessary intermediate step to path compression? Can I skip it and go straight to path compression, or will that be catastrophic?
It was also pointed out that without union by rank, repeated unions could create a linked-list like structure. This means that a single path compression operation could take O(n) in the worst case. This would of course affect future operations, so how this plays out when amortized over many operations is what I'm more interested in.
631
The idea of UNION BY RANK is to ensure that when we combine two trees, we try to keep the overall depth of the resulting tree small. This is implemented as follows: the rank of an element x is initialized to 0 by MAKESET. An element's rank is only updated by the LINK operation.
This can be done in O(E*log(E)) = O(E*log(V^2)) = O(E*2*log(V)) = O(E*log(V)) time. Then iterates through the edges and executes O(E) disjoint-set data structure operations ( 2 find & possibly 1 union on every iteration). The complexity of the operations depends on the disjoint-set implementation.
In the Kruskal's Algorithm, Union Find Data Structure is used as a subroutine to find the cycles in the graph, which helps in finding the minimum spanning tree.
One way to implement disjoint set data structures is to represent each set by a linked list. Each element (object) will be in a linked list and will contain a pointer to the next element in the set and another pointer to the representative of the set.
I googled for "without union by rank" and the second link that came up was this one:
...We close this section with an analysis of union–find with path compression but without union by rank...
The union-find datastructure with path compression but without union by rank processes m find and n-1 link operations in time O((m+n) log n)
181
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
