- show how to implement dictionary in external memoryusing an unordered sequence so that insertions require only ( transfers and searches require ( /btransfers in the worst casewhere is the number of elements and is the number of list nodes that can fit into disk block - change the rules that define red-black trees so that each red-black tree has corresponding ( , treeand vice versa - describe modified version of the -tree insertion algorithm so that each time we create an overflow because of split of node vwe redistribute keys among all of ' siblingsso that each sibling holds roughly the same number of keys (possibly cascading the split up to the parent of vwhat is the minimum fraction of each block that will always be filled using this schemec- another possible external-memory dictionary implementation is to use skip listbut to collect consecutive groups of (bnodesin individual blockson any level in the skip list in particularwe define an order- -skip list to be such representation of skip-list structurewhere each block contains at least / list nodes and at most list nodes let us also choose in this case to be the maximum number of list nodes from level of skip list that can fit into one block describe how we should modify the skip-list insertion and removal algorithms for +skip list so that the expected height of the structure is (logn/logbc- describe an external-memory data structure to implement the queue adt so that the total number of disk transfers needed to process sequence of enqueue and dequeue operations is ( /bc- solve the previous problem for the deque adt -