eschwabe
SuccessorWithDelete.java doesn't stand logarithmic time requirement
Hi, I was looking for a solution for Successor with delete problem and came across this repo. From a glance it looks like your solution is correct but the problem is that union operation in QuickFindUF is linear. Have you figured out the correct answer for this? I'm struggling to understand the motivation of deleting using Union Find data structure.
Hi, I was looking for a solution for Successor with delete problem and came across this repo. From a glance it looks like your solution is correct but the problem is that union operation in QuickFindUF is linear. Have you figured out the correct answer for this? I'm struggling to understand the motivation of deleting using Union Find data structure.
Hi, I am a passerby also looking for solutions for this question. I don't know if you watch through the lecture videos, but operations in weightedQuickUF do take log time. The problem of this implementation is that weightedQuickUF optimizes QuickUF by adding "size" to the components, which, however, doesn't consider the order of the elements. For example, after remove 1,2,3,5,6 then 4, two components {1,2,3,4} and {5,6,7} union(), and {5,6,7} is connected to the root of {1,2,3,4} instead of the opposite. Then if you try to retrieve the successor of any of {5,6,7}, it returns 4, which should be 7. ---------------------------------------update-------------------------------------- A friend of mine figured out a solution. I guess the owner of this repo may not see this "issue" since it's been too long, so I upload this here if you don't mind. The key idea is the same as weightedQuickUF. To make it work, we need an extra array successor[] to record the "successor" of the root element initialized by the same value. When union() happens, update the value of successor[root], which keeps the running time logarithm and avoids the problem I mentioned above (update the smaller to the larger one). Well, my English is poor. Hope these words make sense. :|
