1.Illustrate that via AVL single rotation, any binary search tree T1 can be tran

Question

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.

Explanation / Answer

1) 2 kinds of single rotations can be performed on an AVL tree.

a. Left rotation : In this case the parent of a right child(RC) of an unbalanced binary search tree becomes the left child of RC after rotation.Before rotation, parent of RC < RC ( by binary search tree definition). After rotation, left child of RC which was earlier the parent of RC is less than RC thus satisfying the binary search tree criterion. So the newly created tree after left rotation is still a binary search tree.

b. Right rotation: In this case the parent of a left child(LC) of an unbalanced binary search tree becomes the right child of LC after rotation.Before rotation, parent of LC > LC ( by binary search tree definition). After rotation, right child of LC which was earlier the parent of LC is less than LC thus satisfying the binary search tree criterion. So the newly created tree after right rotation is still a binary search tree.

Hence in both kinds of single rotation operation for binary search trees, the resultant tree is a binary search tree.

Any single rotation operation is O(logN) on an average for BST. ( As rotations may need to be carried for each parent of the node recursively till the root).

To transform a binary search tree into another using single rotations will require at most O(n) rotation operations.

So the total complexity of the entire exercise will be O(nlogn) on average.

So the total complexity of transformation is O(logn) * O(1) = O(log n)

2) Input : 2 sequences S1 and S2 of n elements each where each sequence has a total order relation.

Output : Do sets S1 and S2 contain the same set of elements

Steps:

1) Since S1 and S2 are totally ordered, sort S1 and S2 separately using standard sorting algorithm ( e.g., mergesort - Running time O(nlogn))

2) Once the 2 sets are sorted , pairwise compare each element at specific index for equality

boolean result = "EQUAL"

for ( int i=0; i<n;i++){

if (S1[i]!=S2[i]) then result= "NOT EQUAL";break;

}

print result;

Running time : O(n)

So the combined running time for the solution is O(nlogn).

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.