Suppose I have two union-find trees with roots $x$ and $y$ respectively. I want to join them in constant time (this is normally possible since I already "hold" the roots) but I need $x$ to be the root of the merged tree. I don't know what rank $x$ or $y$ have (or more precisely formulated I need this to work always - for any $x$ and $y$ I want the final tree to have $x$ as its root). Is that possible? I couldn't find a solution to this, but it's really not my day today :)
$\begingroup$
$\endgroup$
0
Add a comment
|
$\begingroup$
$\endgroup$
Unfortunately, that's not possible with the standard data structure for union-find (namely, with the union by rank method).
The data structure has invariants that in some cases require making $y$ be the root (namely, when $x$'s rank is smaller than $y$'s rank, you are required to make $y$ the root). If you force $x$ to be the root in such a situation, then you destroy the invariants, which might make subsequent Find/Union operations slow.
It sounds like you are thinking that perhaps we can reorganize the inner structure of the tree under $x$ or the tree under $y$. Unfortunately, it's not possible to do that in the standard Union-Find data structure. The data structure doesn't have child pointers (doesn't have any way to get from $x$ to its children, or from $y$ to its children), so there is no way for a data structure to change the inner structure of the tree under $x$ or the tree under $y$.
So if you want to achieve this, you will probably need an entirely new data structure. If so, you should probably ask a new question and specify your requirements in terms of the externally observable behavior of the API's, rather than in terms of the internal state of the data structure.
