When doing union by rank, does path compression affect rank(height)? How would y

Question

When doing union by rank, does path compression affect rank(height)? How would you track that in the find function or is it negligible and overlooked?

Explanation / Answer

When unions are done arbitrarily, path compression is a good idea, because there is anabundance of deep nodes and these are brought near the root by path compression. It has beenproven that when path compression is done in this case, a sequence of m operations requiresat most O ( m log n ) time. It is still an open problem to determine what the average-casebehavior is in this situation.Path compression is perfectly compatible with union-by-size, and thus both routines can beimplemented at the same time. Since doing union-by-size by itself is expected to execute asequence of m operations in linear time, it is not clear that the extra pass involved in pathcompression is worthwhile on average. Indeed, this problem is still open. However, as weshall see later, the combination of path compression and a smart union rule guarantees a veryefficient algorithm in all cases.Path compression is not entirely compatible with union-by-height, because path compressioncan change the heights of the trees. It is not at all clear how to re-compute them efficiently.The answer is do not!! Then the heights stored for each tree become estimated heights(sometimes known as ranks ), but it turns out that union-by-rank (which is what this has nowbecome) is just as efficient in theory as union-by-size. Furthermore, heights are updated lessoften than sizes. As with union-by-size, it is not clear whether path compression isworthwhile on average. What we will show in the next section is that with either unionheuristic, path compression significantly reduces the worst-case running time. Worst Case for Union-by-Rank andPath Compression When both heuristics are used, the algorithm is almost linear in the worst case. Specifically,the time required in the worst case is ( m ( m, n )) (provided m n ), where ( m, n ) is afunctional inverse of Ackerman's function, which is defined below:* A (1, j ) = 2 j for j 1 A ( i , 1) = A ( i - 1, 2) for i 2 A ( i, j ) = A ( i - 1, A ( i, j - 1)) for i, j 2 * Ackerman's function is frequently defined with A (1, j ) = j + 1 for j 1. the form in this text grows faster; thus,the inverse grows more slowly. From this, we define ( m, n ) = min{ i 1| A ( i , m/ n ) > log n } You may want to compute some values, but for all practical purposes, ( m, n ) 4, which is allthat is really important here. The single-variable inverse Ackerman function, sometimeswritten as log* n , is the number of times the logarithm of n needs to be applied until n 1.Thus, log* 65536 = 4, because log log log log 65536 = 1. log* 2 65536 = 5, but keep in mindthat 2 65536 is a 20,000-digit number. ( m, n ) actually grows even slower then log* n .However, ( m, n ) is not a constant, so the running time is not linear.

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.