Van Emde Boas木
簡単のため、 log2 m = k がある整数 k {\displaystyle k} について成り立つとする。また、M = 2 とする。vEB 木 T の根は、長さ M {\displaystyle {\sqrt {M}}} の配列 T.children を持つ。T.children[i] は、 i M {\displaystyle i{\sqrt {M}}} から ( i + 1 ) M − 1 {\displaystyle (i+1){\sqrt {M}}-1} までの要素を管理する vEB 木へのポインタを持つ。さらに、T はその最小値と最大値 T.min、T.max と、補助の vEB 木 T.aux を持つ。
vEB 木には以下のようにデータが保存される。
木内の最小値は T.min に、最大値は T.max に入る。 T.min 以外の全ての値 x {\displaystyle x} は、 i = ⌊ x / M ⌋ {\displaystyle i=\lfloor x/{\sqrt {M}}\rfloor } として T.children[i] で管理される。T.aux は、T.children のそれぞれの要素が値を持っているかを管理する。つまり、T.children[j] が空でない場合のみ T.aux は値 j {\displaystyle j} を持つ。