the disjoint sets class path compression the union/find algorithmas described so faris quite acceptable for most cases it is very simple and linear on average for sequence of instructions (under all modelshoweverthe worst case of ( log ncan occur fairly easily and naturally for instanceif we put all the sets on queue and repeatedly dequeue the first two sets and enqueue the unionthe worst case occurs if there are many more finds than unionsthis running time is worse than that of the quick-find algorithm moreoverit should be clear that there are probably no more improvements possible for the union algorithm this is based on the observation that any method to perform the unions will yield the same worst-case treessince it must break ties arbitrarily thereforethe only way to speed the algorithm upwithout reworking the data structure entirelyis to do something clever on the find operation the clever operation is known as path compression path compression is performed during find operation and is independent of the strategy used to perform unions suppose the operation is find(xthen the effect of path compression is that every node on the path from to the root has its parent changed to the root figure shows the effect of path compression after find( on the generic worst tree of figure the effect of path compression is that with an extra two link changesnodes and are now one position closer to the root and nodes and are now two positions closer thusthe fast future accesses on these nodes will pay (we hopefor the extra work to do the path compression as the code in figure showspath compression is trivial change to the basic find algorithm the only change to the find routine (besides the fact that it is no longer const member functionis that [xis made equal to the value returned by findthusafter the root of the set is found recursivelyx' parent link references it this occurs recursively to every node on the path to the rootso this implements path compression when unions are done arbitrarilypath compression is good ideabecause there is an abundance of deep nodes and these are brought near the root by path compression it has been proven that when path compression is done in this casea sequence of figure an example of path compression