Space requirements for van Emde Boas trees This problem

Chapter 20, Problem 20-1

(choose chapter or problem)

Space requirements for van Emde Boas trees This problem explores the space requirements for van Emde Boas trees and suggests a way to modify the data structure to make its space requirement depend on the number n of elements actually stored in the tree, rather than on the universe size u. For simplicity, assume that pu is always an integer. a. Explain why the following recurrence characterizes the space requirement P .u/ of a van Emde Boas tree with universe size u: P .u/ D . pu C 1/P .pu/ C .pu/ : (20.5) b. Prove that recurrence (20.5) has the solution P .u/ D O.u/. In order to reduce the space requirements, let us define a reduced-space van Emde Boas tree, or RS-vEB tree, as a vEB tree V but with the following changes: The attribute V:cluster, rather than being stored as a simple array of pointers to vEB trees with universe size pu, is a hash table (see Chapter 11) stored as a dynamic table (see Section 17.4). Corresponding to the array version of V:cluster, the hash table stores pointers to RS-vEB trees with universe size pu. To find the ith cluster, we look up the key i in the hash table, so that we can find the ith cluster by a single search in the hash table. The hash table stores only pointers to nonempty clusters. A search in the hash table for an empty cluster returns NIL, indicating that the cluster is empty. The attribute V:summary is NIL if all clusters are empty. Otherwise, V:summary points to an RS-vEB tree with universe size pu. Because the hash table is implemented with a dynamic table, the space it requires is proportional to the number of nonempty clusters. When we need to insert an element into an empty RS-vEB tree, we create the RSvEB tree by calling the following procedure, where the parameter u is the universe size of the RS-vEB tree: CREATE-NEW-RS-VEB-TREE.u/ 1 allocate a new vEB tree V 2 V:u D u 3 V:min D NIL 4 V:max D NIL 5 V:summary D NIL 6 create V:cluster as an empty dynamic hash table 7 return V c. Modify the VEB-TREE-INSERT procedure to produce pseudocode for the procedure RS-VEB-TREE-INSERT.V; x/, which inserts x into the RS-vEB tree V , calling CREATE-NEW-RS-VEB-TREE as appropriate. d. Modify the VEB-TREE-SUCCESSOR procedure to produce pseudocode for the procedure RS-VEB-TREE-SUCCESSOR.V; x/, which returns the successor of x in RS-vEB tree V , or NIL if x has no successor in V . e. Prove that, under the assumption of simple uniform hashing, your RS-VEBTREE-INSERT and RS-VEB-TREE-SUCCESSOR procedures run in O.lg lg u/ expected time. f. Assuming that elements are never deleted from a vEB tree, prove that the space requirement for the RS-vEB tree structure is O.n/, where n is the number of elements actually stored in the RS-vEB tree. g. RS-vEB trees have another advantage over vEB trees: they require less time to create. How long does it take to create an empty RS-vEB tree?