（van Emde Boas树的空间需求）这个问题讨论van Emde Boas树的空间需求。并给出一种修改数据结构的方法，使其空间需求依赖元素个数n，而不是全域大小u。为简单起见，假设
总是为整数。
a.解释为什么下列的递归式表示全域大小为u的van Emde Boas的空间需求P(u)。
b.证明上面递归式的解为P(u)=O(u)
为了减少空间需求，定义一棵缩减空间的van Emde Boas树（reduce space van Emde Boas）或RS-vEB树，RS-vEB树是一棵vEB树，但做出了如下修改：
- 属性V.cluster并不是一个指向全域大小的为
- 散列表只存储指向非空簇的指针，在散列表中探索一个空簇，返回NIL，表示这个簇为空。
- 如果所有的簇为空，则属性V.summary为NIL。否则，V.summary指向全域大小为
当需要向空RS-vEB树插入一个元素时，调用下面的过程创建RS-vEB树，其中参数u是RS-vEB树的全域大小：
CREATE-NEW-RS-vEB-TREE(u) 1 allocate a new vEB tree V 2 V.u=u 3 V.min = NIL 4. V.max=NIL 5 V.summary=NIL 6 create V.cluster as an empty dynamic hash table 7 return V
c.修改vEB-TREE-INSERT过程的伪代码，来形成RS-vEB-TREE-INSERT(V,x)的伪代码，实现将x插入RS-vEB树中，并且调用相应的CREATE-NEW-RS-vEB-TREE。
d.修改vEB-TREE-SUCCESSOR的伪代码，来形成RS-vEB-TREE-SUCCESSOR(V,x)的伪代码,实现返回x在RS-vEB树V中的后继，或者如果x在V中无后继，则返回NIL。
e.在简单均匀散列的假设下，证明：你实现的vEB-TREE-INSERT和vEB-TREE-SUCCESSOR的期望运行时间为O(lglgu)。
f.假设从不删除vEB树中的元素，证明：RS-vEB树结构的空间需求为O(n)，其中n是存储在RS-vEB树中的实际元素个数。
g.相比vEB树，RS-vEB树具有另一优点：创建树的时间较少，创建一颗空RS-vEB树需要多长时间？
Proto-vEB-Successor(V, x) if V.u == 2 if x == 0 and V.A[1] == 1 return 1 else return NIL else offset = Proto-vEB-Successor(V.cluster[high(x)], low(x)) if offset != NIL return index(high(x), offset) else succ-cluster = Proto-vEB-Successor(V.summary, high(x)) if succ-cluster == NIL return NIL else offset = Proto-vEB-Minimum(V.cluster[succ-cluster]) return index(succ-cluster, offset) Proto-vEB-Insert(V, x) if V.u == 2 V.A[x] = 1 else Proto-vEB-Insert(V.cluster[high(x)], x) Proto-vEB-Insert(V.summary, high(x))
