2
Up-Trees
•(not as much work as it looks)
•Perform Disjoint Union-Find operations on Up-Tree with path compression and using weight (# of nodes) in merges.
•Starting with empty tree.
•Keep track of (sub)tree weight, and pointers into tree (pointers isn’t too hard)
•Vaguely have a sense of # of operations (e.g. edge traversals)
•For items: a,b,c,d,e,f,g,h,i,j,k
•Union (a,b).  Union (b,c).  Union (d,e).  Union (d,f).  Union (d,j).  Union (d,k).  Union (e,g).  Union (h,i).  Union (c,h).  Union (c,f).  Find (i).  Find (b).  Find (c).  Find (i).  Find (h).