ALGORITHMS AND DATA STRUCTURES II ASSIGNMENT 2
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 2logN.
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.
