University:
University of California, San Diego
Course:
CSE 100/101 | Data Structures and Algorithms
Academic year:

2023
Views:

68

Pages:

2
Author:

anon

Understanding the Union by Rank Heuristic in Union-Find Algorithms The Union-Find algorithm is a data structure used in computer science that keeps track of the division of a set of components into a number of distinct (non-overlapping) subgroups. Two primary operations are provided by the Union-Find algorithm: Find: identifies the subset in which a specific element is included. You can use this to determine whether two elements belong to the same subset. Union: creates a new subset by joining two existing ones. How to keep track of each subset's size (or height) is a crucial factor to take into account while merging two subsets. The Union by Rank heuristic is useful in this situation. What is the Union by Rank Heuristic? A Union-Find method can effectively combine two disjoint sets by using the Union by Rank heuristic. The fundamental concept is to always join the smaller tree's root to the larger tree's root. By doing this, the height of the resulting tree only grows logarithmically as more elements are added to the set. This tactic is carried out by maintaining a second array named rank, where rank[i] is the height of the subtree with root i. When two trees are combined, the roots of the smaller ranking tree are joined to the roots of the larger ranking tree. When the ranks of two trees are equal, either tree's root can be joined to the root of the other tree, increasing the rank of the new tree by one. The Find Operation The fundamental Find operation is comparable to the Find operation in the Union-Find algorithm with the Union by Rank heuristic. The objective is to locate the set's root that contains a particular element. Path compression is used in the implementation to boost performance. The Union Operation There are three primary steps to the Union operation in the Union-Find algorithm with the Union by Rank heuristic: 1) Track down the origins of the two combining elements. 2) Return if the roots are identical because the items are already in the same set. 3) Connect the smaller tree's root to the larger tree's root, and if necessary, update the rank of the final tree. Example Consider the following set of elements: {1, 2, 3, 4, 5, 6}. After calling MakeSet for each element, we have the following data structure: element parent rank 1 2 3 4 5 6 1 2 3 4 5 6 0 0 0 0 0 0 Let's now dial Union (2, 4). 2 and 4 each have 2 and 4 as their roots. We attach the root of 4 to the root of 2 and set parent[4] to 2 because rank[2] = 0 and rank[4] = 0. The final data structure is as follows: element parent rank 1 2 3 4 5 6 1 2 3 2 5 6 0 1 0 0 0 0 Next, let's call Union(1, 3). The roots of 1 and 3 are 1 and 3, respectively. Since rank[1] = 0 and rank[3] = 0, we attach the root of 3 (3) to the root of 1 (1), and set parent[3] = 1.