Consider a binary search tree where each tree node v has a field v.sum which stores the sum of all the keys in the subtree rooted at v.

(a) Modify the RightRotate operation(given below) to properly update the .sum fields so that all the .sum fields of the tree are corrected after applying the RightRotate operation. (Assume that all the .sum fields were correct before the RightRotate operation.) Your modified algorithm should take the same time as the original RightRotate operation. Explain your modification and give pseudo-code for the modified algorithm.

function RightRotate(T,x)

y <-- x.left

b <-- y.right

Transplant(T,x,y)

x.left <--b

if (b != NIL) then b.parent <-- x

y.right <-- x

x.parent <-- y

------------------------------------------

function Transplant(T,u,v)

1 p u.parent;

2 if (p = NIL) then T.root v;

3 else if (u = p.left) then p.left v;

4 else p.right v;

5 if (v != NIL) then v.parent p;

(b) Argue for the correctness of your algorithm. Explain why all the .sum fields are correct after running your modified RightRotate operation.

(c) Analyze the running time of your modified algorithm in terms of the size n and the height h of the binary search tree.