1.Illustrate that via AVL single rotation, any binary search tree T1 can be transformed into another search tree T2 (with the same items) (5 marks).

Give an algorithm to perform this transformation using O(N log N) rotation on average.

2.Suppose you are given two sequences S1 and S2 of n elements, possibly containing duplicates, on which a total order relation is defined. Describe an efficient algorithm for determining if S1 and S2 contain the same set of elements (10 marks).

Analyze the running time of this method (2 marks).

I need a personally answer and do not copy from any other web.Thanks.