Van Emde Boas木
vEB 木上で、x 以上で最小の要素を検索する FindNext(T, x) は次のように実現できる:
・もし x<T.min なら T.min を返す。
・もし x≥T.max ならそのような要素は存在しない。
・ i = ⌊ x / M ⌋ {\displaystyle i=\lfloor x/{\sqrt {M}}\rfloor } として、x<T.children[i].max なら、答えは T.children[i] で再帰的に探索して発見できる。
・そうでなければ、T.aux で i 以上の最小の要素 j を検索して、T.children[j].min を返す。
最悪の場合でも、この関数で再帰呼び出し以外の計算は O(1) で行えて、再帰のたびに木のサイズは元のサイズの平方根となるので、ビット数は半分になる。よって、時間計算量は漸化式 T ( m ) = T ( m / 2 ) + O ( 1 ) {\displaystyle T(m)=T(m/2)+O(1)} で与えられ、このオーダーは O(log m) = O(log log M) となる。