Intersection of Balanced trees Recall the algorithm for finding the union of two AVL trees T1 and T2. In this question, you will develop a similar algorithm for finding the intersection of T1 and T2 : - an AVL tree T that contains key/value pairs that are in both T1 and T2; - if (k,v1)T1 and (k,v2)T2, then (k,v2)T. First we need to modify the algorithm for splitting a tree T with respect to a key k. - Provide pseudocode for split(T,k) that returns a triple (Tk,b) : - Tk : an AVL tree that contains all nodes n from T such that n.key>k, and - b : true, if the key k appears in T, and false, otherwise. Next we will develop an algorithm for joining two AVL trees without the additional key k. - Provide pseudocode for algorithm remove max(T) which returns a pair (T,max) : - T: an AVL tree that contains all key/value pairs of T except for the node max that contains the maximum key in T, and - the node max. - Show how to use remove max to implement the algorithm join(L, G), which takes - L: an ALV tree in which all keys are less than k, and - G : an ALV tree in which all keys are greater than k, and returns an AVL tree T that contains all key/value pairs from L and G. Finally provide pseudocode for intersection (T1,T2) that returns the intersection of T1 and T2