1. Describe your algorithm in English (not with pseudo code);

2. Show why the algorithm is correct;

3. Analyse the complexity of the algorithm.

Design an efficient data structure using (modified) red-black trees that supports the following operations: Insert (x) : insert the key x into the data structure if it is not already there. Delete(x) : delete the key x from the data structure if it is there. Find_Smallest (k) : find the k th smallest key in the data structure. What are the time complexities of these operations? (Hint: for Find_Smallest (k), what if for each node, we add the information of the tree size for the subtree rooted at the node? Is this helpful when searching to decide to go to left subtree or right subtree?)