The median of a set of n distinct integers is the middle element whenthe integers are sorted.
Question:
The median of a set of n distinct integers is the middle element whenthe integers are sorted. For simplicity, we will assume that n is odd, i.e., the medianis at position (n + 1)/2 in sorted order.Example:{−4, 1, 3, 5, 7}, median is 3.
In this problem, we are interested in finding the median of a set of distinct integers stored in two AVL trees. You cannot assume anything about how the integers aredistributed between the two trees (e.g. one might contain n − 1 elements and theother only 1). In addition to the standard pointers to the parent and two children,and the integer itself, each node of the trees also stores the size of the subtree rootedat it. Your task is to design an algorithm that takes these two trees as input andreturns the median of the elements stored in them. For full marks, your algorithm needs to run in O(log n) time.
a) Design an algorithm that solves the problem.
b) Briefly argue the correctness of your algorithm.
c) Analyze the running time of your algorithm.
Expert Answer:
If you modify the AVL tree by storing the size of the sub tree at each node ... View the full answer
