chap advanced tree structures revise the bst class of section to use the splay tree rotations your new implementation should not modify the original bst class adt compare your splay tree against an implementation of the standard bst over wide variety of input data under what conditions does the splay tree actually save time implement city database using the - tree each database record contains the name of the city ( string of arbitrary lengthand the coordinates of the city expressed as integer xand -coordinates your database should allow records to be inserteddeleted by name or coordinateand searched by name or coordinate you should also support region queriesthat isa request to print all records within given distance of specified point implement city database using the pr quadtree each database record contains the name of the city ( string of arbitrary lengthand the coordinates of the city expressed as integer xand -coordinates your database should allow records to be inserteddeleted by name or coordinateand searched by name or coordinate you should also support region queriesthat isa request to print all records within given distance of specified point implement city database using the bintree each database record contains the name of the city ( string of arbitrary lengthand the coordinates of the city expressed as integer xand -coordinates your database should allow records to be inserteddeleted by name or coordinateand searched by name or coordinate you should also support region queriesthat isa request to print all records within given distance of specified point implement city database using the point quadtree each database record contains the name of the city ( string of arbitrary lengthand the coordinates of the city expressed as integer xand -coordinates your database should allow records to be inserteddeleted by name or coordinateand searched by name or coordinate you should also support region queriesthat isa request to print all records within given distance of specified point use the pr quadtree to implement an efficient solution to problem that isstore the set of points in pr quadtree for each pointthe pr quadtree is used to find those points within distance that should be equivalenced what is the asymptotic complexity of this solution select any two of the point representations described in this ( the - treethe pr quadtreethe bintreeand the point quadtreeimplement your two choices and compare them over wide range of data sets describe which is easier to implementwhich appears to be more space efficientand which appears to be more time efficient