In this problem, you will design the data structure for implementing an ADT

called RESTAURANT-SET. Below is the description of the ADT.

Objects: A collection of restaurants in the same city. Each restaurant has the following

attributes:

restaurant.name: a string which is the name of the restaurant. Each restaurant has

a unique name, i.e., no two restaurants have the same name.

restaurant.cost: a decimal value such as 22.99 that denotes the cost of a 1 person

meal at the restaurant. For simplicity, assume that each restaurants cost is unique,

i.e., no two restaurants have the same cost.

restaurant.rating: a decimal value between 0.0 and 5.0, e.g., 0.012, 3.1415926.

For simplicity, assume that each restaurants rating value is unique, i.e., no two

restaurants have the same rating value.

Operations:

GET-RESTAURANT(R, name): returns the restaurant with name name if it exists in the

RESTAURANT-SET R; returns NIL if the restaurant does not exist in R.

ADD-RESTAURANT(R, restaurant): Add a restaurant restaurant to the RESTAURANT-SET

R. You may assume that restaurant has a unique name, a unique cost and a unique

rating.

AVG-COST(R, r1, r2), r1 r2: considers all restaurants that have a rating r such

that r1 r < r2, and returns the average of the meal costs over all these restaurants.

e.g. If R contains the following restaurants: (A, 22, 3), (B, 35, 4.5), (C, 24,

3.9), (D, 30, 4) where each tuple represents (name, cost, rating), then the

query AVG-COST(R, 3, 4) must return the average of the costs of restaurants that

have ratings 3 and < 4, which are A and C. Thus it must return 22+24

2 = 23.

Requirements: Let n be the size of R,

GET-RESTAURANT(R, name) must have average-case runtime O(1).

ADD-RESTAURANT(R, restaurant) must have average-case runtime O(log n).

AVG-COST(R, r1, r2) must have worst-case runtime O(log n).

Give a detailed description of the design of your data structure by answering the following

questions.

(a) Which data structure(s) do you use in your design? What is the key of each data

structure? What attributes does each node in your data structure(s) keep?

(b) Explain concisely in English how your GET-RESTAURANT operation works, and justify

its runtime.

(c) Explain concisely in English how your ADD-RESTAURANT operation works, and justify its

runtime. In particular, explain why all the attributes kept in each node can be maintained

efficiently upon the addition of the new node.

(d) Explain how your AVG-COST operation works and write the pseudocode of this

operation, then justify its runtime.

Hi, I am a bit confused about those data structures, I tried to use a lot different data structures such as hash table, linked list, BST, etc. But none of them satisfies all the requirements. Can you help me with this please?