- if the approach described in the previous problem were implemented as part of the treemap classwhat additional modifications (if anywould be necessary to subclass such as avltreemap in order to maintain the efficiencyc- for standard binary search treetable claims ( )-time performance for the delete(pmethod explain why delete(pwould run in ( time if given solution to exercise - - describe modification to the binary search tree data structure that would support the following two index-based operations for sorted map in (htimewhere is the height of the tree at index( )return the position of the item at index of sorted map index of( )return the index of the item at position of sorted map - draw splay treet together with the sequence of updates that produced itand red-black treet on the same set of ten entriessuch that preorder traversal of would be the same as preorder traversal of - show that the nodes that become temporarily unbalanced in an avl tree during an insertion may be nonconsecutive on the path from the newly inserted node to the root - show that at most one node in an avl tree becomes temporarily unbalanced after the immediate deletion of node as part of the standard delitem map operation - let and be ( trees storing and entriesrespectivelysuch that all the entries in have keys less than the keys of all the entries in describe an (log log )-time method for joining and into single tree that stores all the entries in and - repeat the previous problem for red-black trees and - justify proposition - the boolean indicator used to mark nodes in red-black tree as being "redor "blackis not strictly needed when we have distinct keys describe scheme for implementing red-black tree without adding any extra space to standard binary search tree nodes - let be red-black tree storing entriesand let be the key of an entry in show how to construct from in (log ntimetwo red-black trees and such that contains all the keys of less than kand contains all the keys of greater than this operation destroys - show that the nodes of any avl tree can be colored "redand "blackso that becomes red-black tree