1. Starting with an empty tree, construct a red-black tree by inserting the following keys in

the order given: 2; 1; 4; 5; 9; 3; 6; 7. If an insertion causes the tree to violate the properties

of a red-black tree, then perform the necessary restructuring.

2. Prove that the height of a red-black tree with N nodes is at most 2 log N.

3. Consider the following Reverse-Delete algorithm: Remove edges in the decreasing order of

weight skipping those whose removal would disconnct the graph. Prove that this algorithm

always outputs the MST. You can assume that the edge weights are distinct.

4. Prove that if all the edges of a graph G have distinct weights, the MST of G is unique.

5. A minimum bottleneck spanning tree (MBST) of a weighted, undirected graph G is a

spanning tree in which the edge of maximum weight is as small as possible. Give a counter

example to show that a MBST of G is not always a MST of G.

Sale!