Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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 .
share|improve this question
add comment

1 Answer

up vote 4 down vote accepted

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.

share|improve this answer
    
What about my second question ? Would you please clear my doubts on the usage of the word "each " ? –  Geek Oct 20 '12 at 18:11
    
"f 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." . can you please explain this point –  Geek Oct 20 '12 at 18:13
    
I dont get your second question. Regarding your second comment, I advise you to read first about vEB trees, i.e. the wikipedia article. If then something is unclear, ask a new question. Explaining vEB trees in one answer (that is what you are asking for) is too broad for this format. –  A.Schulz Oct 20 '12 at 19:52
    
I am reading up vEB from CLRS book. There they define the proto vEB tree but I didn't find min and max for every block being defined . since every bit vector is a 0 or a 1 , what exadctly you mean by min/max here ? –  Geek Oct 22 '12 at 9:07
    
@ A.Schulz I have deleted my second question as I understood that concept now . –  Geek Oct 22 '12 at 9:07
show 3 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.