(Q1-6 pts) Use the Selection Sort algorithm to sort the array assigned to you. Show the contents of the array in each of the iterations of the algorithm. (Q2-9 pts) Construct a height-balanced binary search tree of the sorted array of (Q1). Show all the steps in the construction process as the binary search tree evolves. If you just show the final binary search tree and not the binary search tree as it evolves during the construction process, you will get a ZERO. (Q3-8 pts) For the binary search tree of (Q2), determine the average number of comparisons for a successful search and the average number of comparisons for an unsuccessful search. Show all the steps. (Q4-9 pts) Write the pre-order, in-order and post-order traversal of the "data" in the binary search tree of (Q3). (Q5-10 pts) Delete the root node of the binary search tree of (Q2) and show the resulting binary search tree. Is the binary search tree still height-balanced after the change in its structure? Show your calculations to check for the height-balanced property. (Q6-8 pts) Consider the skeleton of the binary tree given below. Let the data for the nodes in this binary tree correspond to those at the indexes in the array assigned to you. Transform this binary tree to a binary search tree by preserving its structure, and show the resulting binary search tree along with the data of the nodes. Show all the work. 8 11 0 1 1 17 2 19 3 28 4 29 5 29 6 36 7 38 8 42 9 | 43 10 47 11 48