y-fast tries This problem investigates D. Willards y-fast

Chapter 20, Problem 20-2

(choose chapter or problem)

y-fast tries This problem investigates D. Willards y-fast tries which, like van Emde Boas trees, perform each of the operations MEMBER, MINIMUM, MAXIMUM, PREDECESSOR, and SUCCESSOR on elements drawn from a universe with size u in O.lg lg u/ worst-case time. The INSERT and DELETE operations take O.lg lg u/ amortized time. Like reduced-space van Emde Boas trees (see 20-1), yfast tries use only O.n/ space to store n elements. The design of y-fast tries relies on perfect hashing (see Section 11.5). As a preliminary structure, suppose that we create a perfect hash table containing not only every element in the dynamic set, but every prefix of the binary representation of every element in the set. For example, if u D 16, so that lg u D 4, and x D 13 is in the set, then because the binary representation of 13 is 1101, the perfect hash table would contain the strings 1, 11, 110, and 1101. In addition to the hash table, we create a doubly linked list of the elements currently in the set, in increasing order. a. How much space does this structure require? b. Show how to perform the MINIMUM and MAXIMUM operations in O.1/ time; the MEMBER, PREDECESSOR, and SUCCESSOR operations in O.lg lg u/ time; and the INSERT and DELETE operations in O.lg u/ time. To reduce the space requirement to O.n/, we make the following changes to the data structure We cluster the n elements into n= lg u groups of size lg u. (Assume for now that lg u divides n.) The first group consists of the lg u smallest elements in the set, the second group consists of the next lg u smallest elements, and so on. We designate a representative value for each group. The representative of the ith group is at least as large as the largest element in the ith group, and it is smaller than every element of the .i C1/st group. (The representative of the last group can be the maximum possible element u 1.) Note that a representative might be a value not currently in the set. We store the lg u elements of each group in a balanced binary search tree, such as a red-black tree. Each representative points to the balanced binary search tree for its group, and each balanced binary search tree points to its groups representative. The perfect hash table stores only the representatives, which are also stored in a doubly linked list in increasing order. We call this structure a y-fast trie. c. Show that a y-fast trie requires only O.n/ space to store n elements. d. Show how to perform the MINIMUM and MAXIMUM operations in O.lg lg u/ time with a y-fast trie. e. Show how to perform the MEMBER operation in O.lg lg u/ time. f. Show how to perform the PREDECESSOR and SUCCESSOR operations in O.lg lg u/ time. g. Explain why the INSERT and DELETE operations take .lg lg u/ time. h. Show how to relax the requirement that each group in a y-fast trie has exactly lg u elements to allow INSERT and DELETE to run in O.lg lg u/ amortized time without affecting the asymptotic running times of the other operations.