1. In the range searching problem, a dynamic set S of points is stored in a data structure so that the points contained in a query rectangle R can be reported or counted efficiently. The data structure is constructed and updated by inserting and deleting points. The query R is specified by the coordinates (x0, y0) and (x1, y1) of its bottom left and top right corners respectively. While this problem can be solved by testing each input point against the query rectangle, you will explore a more efficient solution based on augmented red-black trees. In your solution each node of the tree will store a single point from S and use xcoordinate as the key. Furthermore each node v will be augmented with the y- coordinates of the lowest and highest points in the subtree rooted at v. The following operations must be supported:

• Insert(p, T) :insert point p int tree T
• Delete(p, T): delete point p from tree T
• Inside(R, T): report all points from T obtained inside query rectangle R

1. (a)Explain how to maintain the augmented information during Insert or Delete.
2. (b)What are the time complexities of insert and delete?
3. (c)Describe how to use the augmented data structure in order to speed up the execution of Inside query