I'm reviewing my background in Algorithms and DS design. Specifically I never went through the van Emde Boas Tree. Though I can undestand the proto-vEB with related picture. I'm struggling to understand the actual data structure. I have no clue how the "min" and "max" members are actually used, I'm not talking about the procedures but just how the following picture is supposed to be interpreted. Can anyone help me with this?
If you haven't done so, I suggest you read chapter 20 from the beginning. They develop the final data structure bit by bit, supposedly for didactic reasons.
In 20.3.1, they write:
min stores the minimum element in the vEB tree, and max stores the maximum element in the vEB tree. Furthermore, the element stored in min does not appear in any of the [subtrees].
What might confuse you is that the actual elements to not appear. As explained earlier in the chapter, the elements are encoded by position: the domain of the tree is $[0..15]$, and the subset is essentially encoded by a bit vector stored in the leaves of the tree. Figure 20.4 is annotated helpfully in this regard; note that the minimums are moved up to the
min fields here, though.
In the full VEB tree, the encoding itself is a little tricky. Here goes:
Here is how you read the tree (ignore the dark summary nodes for this purpose):
udenotes the size of the domain of a node.
- The root has domain
- The domain of a node
cluser[i]is the the
i-th chunk of size
cluser[i].uin the domain of its parent.
- If they are not
maxare indices into the domain of the node.
nil, the node represents no elements.
0; it represents element
0 + 1*4 * 0 = 3.
0 + 0*4 + 1*2 + 0/1 = 2/3are both not in the node.
2is in the set anyway, since it's represented by
0 + 3*4 + 2 = 14is in the set.
0 + 3*4 + 1*2 + 1 = 15is in the set.