Question 2. (1 marks) Consider an abstract data type that consists of a set S of integers on which the following operations can be performed: Add(i) : Adds the integer i to S. If this integer already is in S, then S does not change Average(t) : Returns the average of all elements of S that are less than or equal to the integer t. If all the elements of S are greater than t, then return 0. Describe how to implement this abstract data type using an augmented AVL tree T. Each operation should run in O(logn) worst-case time, where n = |S|. Since this implementation is based on a data structure and algorithms described in class and in the AVL handout, you should focus on describing the extensions and modications needed here. a. Give a precise and full description of your data structure. In particular, specify what data is associated with each node, specify what the key is at each node, and specify what the auxiliary information is at each node. In particular, what is (are) the augmented eld(s), and what identity should this (these) elds satisfy. Illustrate this data structure by giving an example of it (with a small set of your own choice). b. Describe the algorithm that implements each one of the two operations above, and explain why each one takes O(logn) time in the worst-case. Your description and explanation should be in clear and concise English. For the operation Average, you should also give the algorithms high-level pseudocode.