How to read off the set represented by a van-Emde-Boas tree?

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):

• u denotes the size of the domain of a node.

• The root has domain [0..u-1].

• The domain of a node cluser[i] is the the i-th chunk of size cluser[i].u in the domain of its parent.

• If they are not nil, min and max are indices into the domain of the node.

• If min and max are nil, the node represents no elements.

Examples:

• root.cluster[1].min is 0; it represents element 0 + 14 0 = 3.

• root.cluster[0].cluster[1].min/max are nil; therefore 0 + 04 + 12 + 0/1 = 2/3 are both not in the node.

But 2 is in the set anyway, since it's represented by root.min!

• root.cluster[3].min is 2; therefore, 0 + 3*4 + 2 = 14 is in the set.

• root.cluster[3].cluster[1].min/max are 1; therefore 0 + 34 + 12 + 1 = 15 is in the set.

StackExchange Computer Science Q#88970, answer score: 4