# Explanation of recursive structure of Van Emde Boas Tree

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 ﬁrst 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 .

## 1 Answer

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.

• 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