1. Devise a series of equivalence statements for a collection of sixteen items that yields a tree of height 5 when both the weighted union rule and path compression are used. What is the total number of parent pointers followed to perform this series?
2. One alternative to path compression that gives similar performance gains is called path halving. In path halving, when the path is traversed from the node to the root, we make the grandparent of every other node i on the path the new parent of i. Write a version of FIND that implements path halving. Your FIND operation should work as you move up the tree, rather than require the two passes needed by path compression.