occupies words and that each pointer occupies one word of storage what is the gain in storage when using binary tree versus an -ary tree assume that tree is built upon the following definition of recursive data structure (see exercise formulate procedure to find an element with given key and to perform an operation on this element rectype tree record xintegerleftrighttree end in certain file system directory of all files is organized as an ordered binary tree each node denotes file and specifies the file name andamong other things the date of its last accessencoded as an integer write program that traverses the tree and deletes all files whose last access was before certain date in tree structure the frequency of access of each element is measured empirically by attributing to each node an access count at certain intervals of timethe tree organization is updated by traversing the tree and generating new tree by using the program of straight search and insertionand inserting the keys in the order of decreasing frequency count write program that performs this reorganization is the average path length of this tree equal toworseor much worse than that of an optimal tree the method of analyzing the tree insertion algorithm described in sect can also be used to compute the expected numbers cn of comparisons and mn of moves (exchangeswhich are performed by quicksortsorting elements of an arrayassuming that all npermutations of the keys are equally likely find the analogy and determine cn and mn draw the balanced tree with nodes which has the maximum height of all -node balanced trees in which sequence do the nodes have to be inserted so that the avl-insertion procedure generates this tree find sequence of insertion keys so that the procedure for insertion in an avl-tree performs each of the four rebalancing acts (lllrrrrlat least once what is the minimal length for such sequence find balanced tree with keys and permutation of these keys so thatwhen applied to the deletion procedure for avl-treesit performs each of the four rebalancing routines at least once what is the sequence with minimal length what is the average path length of the fibonacci-tree write program that generates nearly optimal tree according to the algorithm based on the selection of centroid as root assume that the keys are inserted into an empty -tree of order which keys cause page splits to occurwhich keys cause the height of the tree to increaseif the keys are deleted in the same orderwhich keys cause pages to be merged (and disposedand which keys cause the height to decreaseanswer the question for (aa deletion scheme using balancingand (ba scheme whithout balancing (upon underflowa single item only is fetched from neighboring page write program for the searchinsertionand deletion of keys in binary -tree use the node type and the insertion scheme shown above for the binary -tree find sequence of insertion keys whichstarting from the empty symmetric binary -treecauses