1
$\begingroup$

The universe size $u$ in vEB trees is square rooted at each level until $u = 2$. So, unlike search trees, the branching factor is different at each level.

enter image description here

The height of the tree is $h = \lg \lg(u)$ and $u$ is an even power of 2, $u = 2^{2^k}$. I tried to calculate the count using the sum:

$$\sum_{i=1}^{h-1} 2^i\,2^{i + 1}$$

But it doesn't work. Any idea on how to do the math?



Edit:

Sorry for the confusion that might be caused by the illustration. The illustration is based on the CLRS book's implementation of VEB trees, but the summary nodes are not shown. Thinking again about it now, I would like to know the count of all the nodes including the summary nodes and their tree nodes, as well as, the count of just the nodes without the summary.

$\endgroup$
1
$\begingroup$

The nice picture in the question does not include the summary nodes nor the min and max fields, both of which are indispensable components of a van Emde Boas tree (vEB tree). A better illustration might be the following picture taken from how to read off the set represented by a van-Emde-Boas tree, which was drawn by Raphael based on a figure in CLRS, where a number in orange is drawn at a min field that marks its presence in the set of integers being represented.

van Emde Boas tree at https://cs.stackexchange.com/questions/88970/how-to-read-off-the-set-represented-by-a-van-emde-boas-tree How many nodes are there in the vEB tree implemented like the illustration above?

There are $1 + 5 + 5 \times 3 = 21$ nodes in the illustration above.

For the sake of simplicity, let $w=2^h$ and $u=2^w=2^{2^h}$. A vEB tree over the universe $\{0,1,\cdots, u-1\}$ is of depth $h=\log\log u$.

  • There is one node of depth 0, which is the root node.
  • There are $2^{2^{h-1}} + 1$ nodes of depth 1.
  • Each node of depth 1 has $2^{2^{h-2}} + 1$ child nodes of depth 2.
  • ...
  • Each node of depth i has $2^{2^{h-i-1}} + 1$ child nodes of depth $i+1$.
  • ...
  • Each node of depth $h-1$ has $2^{2^{h-h}}+1=3$ child nodes of depth $h$.

In total, the number of all nodes is $$1 + \sum_{i=1}^{h}\prod_{k=1}^i(2^{2^{h-k}} + 1)=(2^{2^h} - 1)\sum_{i=0}^{h}\frac1{2^{2^i} - 1}\tag{1}$$ which is 1, 4, 21, 358, 92007, 6029862760, 25898063359598159721, $\cdots$ for $h=0,1,2,3,4,5,6,\cdots$ respectively. When $h\ge4$, the number of nodes is about $1.404u$.

Similarly, the number of all summary nodes is, for $h\ge1$, $$1 + \sum_{i=2}^{h}\prod_{k=1}^{i-1}(2^{2^{h-k}} + 1)=(2^{2^{h}} - 1)\sum_{i=1}^{h}\frac1{2^{2^i} - 1},\tag{2}$$ which is 0, 1, 4, 21, 358, 92007, 6029862760, $\cdots$ for $h = 0,$$1, 2,3,4,5,$$6,\cdots$ respectively.

What is the number of all non-summary nodes? Subtracting (2) from (1), we obtain

$$(2^{2^{h}} - 1)\left.\frac1{2^{2^i} - 1}\right|_{i=0}=2^{2^h}-1=u-1.$$

The formula also hold for $h=0$. So we have obtained the following surprising formula. $$\text{the number of non-summary nodes in a vEB tree of universe size } u=2^{2^h}\text{ is }u-1.$$


Every node at the same depth use the same amount of space. Nodes at a smaller depth may use much more space than those at a larger depth. For example, for $h=5$, the root node contains a bit-array of size 65536 but a leaf node just contains several words. Since the number of nodes that use bigger space decreases very quickly as their depth becomes smaller, the total space used is $O(u)$.


Exercise. The number of all leaf nodes, which are vEB trees of universe size 2 in a vEB tree of universe size $u=2^{2^h}$ is $u-1$.

$\endgroup$
  • $\begingroup$ Thank you for your answer. I edited my question, please have a look. I made the illustration myself and did not include the summary points deliberately, because I was only interested in counting the main nodes. Now you mentioned it though I would like to also know how to count the overall nodes. Also can the sum of the product in the formula you suggested be simplified? $\endgroup$ – razzak Jul 29 at 13:11
  • $\begingroup$ I think that by excluding the summary nodes, the count would become $1 + \sum_{i=1}^{h}\prod_{k=1}^i 2^{2^{h-k}}$ right?, which looks possible to simplify "working on it :)", and also because I think the count of summary nodes is a constant fraction of the cluster nodes count, although didn't figure out that constant yet. $\endgroup$ – razzak Jul 30 at 22:38
  • $\begingroup$ Thanks for your insistence. I just found that the number of all non-summary nodes as well as the number of all leaf nodes is $u-1$ for universe size $u=2^{2^h}$. $\endgroup$ – Apass.Jack Jul 31 at 1:38
  • $\begingroup$ $u-1$ is the count of leaf nodes only and not the overall count of non-summary nodes. I found out that the count of the non-summary nodes is $u - \sqrt{u} + 1$ link. $\endgroup$ – razzak Jul 31 at 20:32
  • $\begingroup$ I think we might be confused about the non-summary node definition, I use this term to describe all light-gray nodes in Raphael's illustration except those inside the summary trees. So in this illustration above there are 13 non-summary nodes and this formula $u - \sqrt{u} + 1$ is able to calculate it successfully. $\endgroup$ – razzak Aug 1 at 1:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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