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 :)


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.