advanced data structures and implementation exercises  prove that the amortized cost of top-down splay is (log nprove that there exist access sequences that require log rotations per access for bottom-up splaying show that similar result holds for top-down splaying modify the splay tree to support queries for the kth smallest item compareempiricallythe simplified top-down splay with the originally described top-down splay write the deletion procedure for red-black trees prove that the height of red-black tree is at most log nand that this bound cannot be substantially lowered show that every avl tree can be colored as red-black tree are all red-black trees avldraw suffix tree and show the suffix array and lcp array for the following input stringsa abcabcabc mississippi once the suffix array is constructedthe short routine shown in figure can be invoked from figure to create the longest common prefix array in the codewhat does rank[irepresentb suppose that lcp[rank[ih show that lcp[rank[ + > show that the algorithm in figure correctly computes the lcp array prove that the algorithm in figure runs in linear time suppose that in the linear-time suffix array construction algorithminstead of constructing three groupswe construct seven groupsusing for sk show that with recursive call to we have enough information to sort the other four groups and show that this partitioning leads to linear-time algorithm implement the insertion routine for treaps nonrecursively by maintaining stack is it worth the effort we can make treaps self-adjusting by using the number of accesses as priority and performing rotations as needed after each access compare this method with the randomized strategy alternativelygenerate random number each time an item is accessed if this number is smaller than ' current priorityuse it as ' new priority (performing the appropriate rotation show that if the items are sortedthen treap can be constructed in linear timeeven if the priorities are not sorted implement some of the tree structures without using the nullnode sentinel how much coding effort is saved by using the sentinel