                                                                         Assignment 4 Solutions
1.
      find the first element for which key is equal to k1.
        store the element in the iterator.(If there are no element s with key k1 , take the element with the lowest key value
        in the range k1 and k2.)
        do an inorder traversing starting from this node.Compare each node with k2.If this nodes key is greater than k2 then stop
        traversing.Otherwise store this in the iterator.

Finding the first node whose key value is greater than k1 will take O(logn ) time. The time for the traversing is O(s).So
Total time is O(log n + s).

2.
At most one trinode restructure operation is needed to restore balance after any insertion.The tree is balanced prior to insertion of an item.After insertion the tree may or may not become unbalanced.If the tree is unbalanced , we find the first node starting from the node that is inserted just now, where the unbalance occured.We do trinode restructuring on the subtree rooted at this node where unbalanced occured.The trinode restructure replaces this tree with a balanced tree of height one less than the original tree.So all the ancestors which became unbalanced after this insertion also becomes balanced.So with at most one trinode operation we can restore the balance after any insertion.See the following two examples.It shows the restructuring of two unbalanced trees.

Eg:1

Eg:2

3.
Assume that T and U have heights h_t and h_u and h_t > h_u .Remove the smallest element from U .I Insert this element into
right most node of tree T at height 'h_t - h_u -1 '. Link this node to the root of tree U.

The remove operation on U takes O(log m) time and the insert operation on T takes O(log n) time. So Running time of this
Algorithm is O(log n + log m ).

5.
v is partitioned into v' and v'' .Out of the keys k1, k2 , k3,k4 , k2 is stored at v's parent. K2 is chosen because it is given that v is
partioned into a 2 - node and a 3 -node.The key stored at the root must be greater than keys in v' and lesser than keys in v''.

6.
Consider the set of items < 44 28 32 15 88 10 53 >
Figure below shows two different order of insertions and the resulting binary search trees .The trees are different .So the professor Amongus is wrong.

7. Consider the set of items < 44 28 32 15 88 10 53 >
Figure below shows two different order of insertions and the resulting AVL trees .The trees are different .So the professor Amongus is wrong. again !!!!!

8.
Consider the set of items < 44 28 32 15 88 10 53 >
Figure below shows two different order of insertions and the resulting (2,4) trees .The trees are different .So the professor Amongus is wrong. again !!!!!