Explanation of recursive structure of Van Emde Boas Tree

Problem Detail: 

From Van Emde Boas trees lecture:

We will use the idea of superimposing a tree of degree ${u^{1/2}}$ on top of a bit vector, but shrink the universe size recursively by a square root at each tree level. The ${u^{1/2}}$ items on the first level each hold structures of ${u^{1/4}}$ items, which hold structures of ${u^{1/8}}$ items, and so on, down to size 2. I have a question regarding van Emde Boas trees :

1. How is the universe size getting reduced ? Aren't we just spreading the universe keys which is always constant at $u$ to different levels ? I can not understand the idea of "shriniking" the universe size . I find similar language is used in defining the recursive structure for Van Emde Boas tree in Introduction to Algorithms by CLRS also .

Asked By : Geek

Answered By : A.Schulz

Well the crucial idea about vEB trees is the following: You store all the elements as a 0/1 bitvector of size $s$. For example the vector $(0,1,1,0)$ denotes that in your universe of size $s=4$, the third and second elements are present. Now you subdivide the vectors in blocks of size $\sqrt{s}$ and for every block you also store a flag, if there is at least one $1$ in the block. This gives you a set of $\sqrt{s}$ flag bits. If you store also the $\min$ and $\max$ for every block, then you can determine in which block you have to continue your search for the successor after either perform a successor query in the block of your query element or in the flag bit vector.

This implies that the sup-problem you are requesting has size $\sqrt{s}$. But this is the same statement as saying that you go from a $k$-bit universe to a $k/2$-bit universe.

And this is meant by shrinking the universe.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/6192