3 ms·

If at some point you have a cycle, you can then reparent and remove the cycle, right? This structure in general then can encode transitive relations effectively

• thaumasiotes 4y ago
  > If at some point you have a cycle, you can then reparent and remove the cycle, right? You'd never have a cycle. The way a cycle would theoretically arise would have to be joining something to its own child. But you don't naively join the two objects you're given - you find their root objects, and join those. If - as would be necessary for a cycle to form - they have the same root, you can return without doing anything. If we call unite(a,b) unite(b,c) unite(c,a) then we should end up with this structure: c / \ b a With parents on the right, the structure will be a-b after the first call and a-b-c after the second call. The reason we end up with a shallower tree after the third call is that when a is passed to unite, we call find on it and it gets reparented directly to c. Then, c (the representative for c) and c (the representative for a) are already related, so we don't adjust the structure further. > This structure in general then can encode transitive relations effectively? Well... no. This structure embodies the concept of an equivalence relation. You wouldn't be able to use it to express a general transitive relation, only a transitive relation that is also symmetric and reflexive.
  • kizer 4y ago
    Thanks!