Algorithm I, Part I — Union By Height

Q: Union-by-height. Develop a union-find implementation that uses the same basic strategy as weighted quick-union but keeps track of tree height and always links the shorter tree to the taller one. Prove a lgN upper bound on the height of the trees for N sites with your algorithm.

(Java Code on github at the bottom of the post. )

My thoughts and solutions:

This one should be simple if you know how to union by size. Just change the array that holds the size of tree to an array that holds the height of the tree. And if a shorter tree connects to a taller tree, the height of the new tree is the same as the old tall tree. So when does the tree height increase? Well, the answer is that when two trees with the same height union together.

As for the upper bound of the height of the tree for N sites, let’s think about the worst case that we union objects in pairs to create trees with the same height and keep doing it until we end up with a single tree. The tree height always increases, but at most lgN times (since we are union things in pair). If on any level, we break this rule, we increase less.

Level 1: 1    2    3   4    5   6   7   8

Level 2: 1-2    3-4   5-6    7-8

Level 3: 1-2-3-4   5-6-7-8

Level 4: 1-2-3-4-5-6-7-8

Code on github:

Enhanced by Zemanta