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...

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.