tailieunhanh - Lecture Data Structures: Lesson 36

Lecture Data Structures: Lesson 36 provide students with knowledge about union by size; maintain sizes (number of nodes) of all trees, and during union; make smaller tree the subtree of the larger one; implementation: for each root node i, instead of setting parent[i] to -1, set it to -k if tree rooted at i has k nodes; . | Running Time Analysis Union is clearly a constant time operation. Running time of find i is proportional to the height of the tree containing node i. This can be proportional to n in the worst case but not always Goal Modify union to ensure that heights stay small Lecture Data Structures Dr. Sohail Aslam Union by Size Maintain sizes number of nodes of all trees and during union. Make smaller tree the subtree of the larger one. Implementation for each root node i instead of setting parent i to -1 set it to -k if tree rooted at i has k nodes. This also called union-by-weight. Union by Size union i j root1 find i root2 find j if root1 root2 if parent root1 Union by Size 1 2 3 4 5 6 7 8 -1 -1 -1 -1 -1 -1 -1 -1 1 2 3 4 5 6 7 8 Eight elements initially in different sets. Union by Size 1 2 3 4 5 7 8 6 -1 -1 -1 -2 -1 4 -1 -1 1 2 3 4 5 6 7 8 Union 4 6 Union by Size 1 2 4 5 7 8 3 6 -1 -2 2 -2 -1 4 -1 -1 1 2 3 4 5 6 7 8 Union 2 3 Union by Size 2 4 5 7 8 3 1 6 4 -2 2 -3 -1 4 -1 -1 1 2 3 4 5 6 7 8 Union 1 4 Union by Size 4 5 7 8 2 1 6 3 4 4 2 -5 -1 4 -1 -1 1 2 3 4 5 6 7 8 Union 2 4 Union by Size 4 7 8 2 1 6 5 3 4 4 2 -6 4 4 -1 -1 1 2 3 4 5 6 7 8 Union 5 4 Analysis of Union by Size If unions are done by weight size the depth of any element is never greater than log2n. Analysis of Union by Size Intuitive Proof Initially every element is at depth zero. When its depth increases as a result of a union operation it s in the smaller tree it is placed in a tree that becomes at least twice as large as before union of two equal size trees . How often can each union be done - log 2n times because after at most log2n unions the tree will contain all n elements. Union by Height Alternative to union-by-size strategy maintain heights During union make a tree with smaller height a subtree of the other. Details are left as an exercise. Sprucing up Find So far we have tried to optimize union. Can we optimize find Yes using path compression or compaction . Sprucing up Find During find i as