Question

Suggest a data structure that supports the following operations on the grades that a student at the university receives. Assume that the total number n of exams that the student might take is large. The data structure should support the following operations: (each in O(log n) time, where n is the number of exams taken). (a) insert(exam date, exam-grade). This operation informs the data structure that the student received at date exam date the grade exam-grade. (b) average (datei, datez). As a response to this operation the data structure should answer what is the average of all grades that are received between the dates date and date2. Assume again that all dates are different, and for simplicity, assume that no exam took place in date, nor in date2. Hint: Start by solving the simpler task of being able to report the number of exams that took place between date, to date,

Answer 1

Answer:

I would suggest a balanced binary search tree or an AVL tree.

AVL tree is a self balancing binary tree. It maintains its BST properties with an additional property that difference between height of left sub-tree and right sub-tree of any node can’t be more than 1.

a). The time complexity for insertion in an AVL tree is O(log n)

b). For searching also, time complexity is O(log n) because the the tree is balanced.

Explanation: