Disjoint Set Union with Randomized Linking
Ashish Goel, Sanjeev Khanna, Daniel H. Larkin, Robert Endre Tarjan · 2015
A classic result in the analysis of data structures is that path compression with linking by rank solves the dis-joint set union problem in almost-constant amortized time per operation. Recent experiments suggest that in practice, a näıve linking method works just as well if not better than linking by rank, in spite of being theo-retically inferior. How can this be? We prove that ran-domized linking is asymptotically as efficient as linking by rank. This result provides theory that matches the experiments, which implicitly do randomized linking as a result of the way the input instances are generated. 1 Disjoint Set Union via Compressed Trees The disjoint set union problem, also called the union-find problem, is to maintain a collection of disjoint sets, each with a distinguished root element, under an intermixed sequence of the following two kinds of operations: Find (x): Return the root of the set containing element x. Unite (x, y): If elements x and y are in the same set, return false; otherwise, form the union of the sets containing x and y (destroying the old sets), choose a root for the new set, and return true. Initially each set is a singleton, whose only element is its root. In each Unite, the implementation is free to choose the root of the new set. Information associated with a set can be stored in its root. The compressed tree solution to this problem [6] represents each set by a rooted tree whose nodes are the elements of the set and whose root is the root of