Van Emde Boas木
vEB 木 T への値 x の挿入操作 insert(T, x) は次のように実現できる:
もし T が空なら、T.min = T.max = x として、操作は終了する。
もし x<T.min なら、T.min を対応する部分木 T.children[i] に挿入して、T.min = x とする。もし T.children[i] がもともと空なら、T.aux に i を挿入する。
それ以外の場合、対応する部分木 T.children[i] に x を挿入して、もし T.children[i] がもともと空なら、T.aux に i を挿入する。x>T.max なら、T.max = x とする。 とする。
空の vEB 木への要素の挿入は O(1) で済む。もしアルゴリズムが再帰呼び出しを二回行っても、一度目の再帰呼び出しは空の vEB 木への挿入であるから、前節と同様に時間計算量の漸化式は T ( m ) = T ( m / 2 ) + O ( 1 ) {\displaystyle T(m)=T(m/2)+O(1)} となる。
vEB 木は、順序付き連想配列の機能を持ち、挿入・削除・検索の機能を持つ。また、これに加えて、与えられた数の周辺の要素の検索も可能である。
挿入:m ビットのキーと、対応する値のペアを挿入する
削除:与えられたキーを持つ要素を削除する
検索:キーから要素を検索する
後方検索:k 以上で最小のキーを持つ要素を検索する
前方検索:k 以上で最大のキーを持つ要素を検索する
さらに、vEB 木は最小値・最大値のクエリにも対応可能である。 最小値と最大値は木に変数として保存されているため、これらのクエリには O(1) で応答できる。
木が大きくなるにつれて、多くの部分木が再利用されるようになり、M 個の要素すべてを持つ木でも、O(M) のメモリしか消費されない。さらに、二分探索木と異なり、このメモリの大部分はデータそのものの保存に使われる。vEB 木全体で持つポインタは、要素が数億あったとしても数千個に収まる。
これはポインタを用いて実装され、空間計算量は O(M) = O(2) となり、キーのある空間の大きさに比例する。これは次のように示される。
空間計算量に対して漸化式を立てると S ( M ) = O ( M ) + ( M + 1 ) ⋅ S ( M ) {\displaystyle S(M)=O({\sqrt {M}})+({\sqrt {M}}+1)\cdot S({\sqrt {M}})} となり、これを解くと S ( M ) ∈ ( 1 + M ) log  log  M + log  log  M ⋅ O ( M ) {\displaystyle S(M)\in (1+{\sqrt {M}})^{\log \log M}+\log \log M\cdot O({\sqrt {M}})} となる。さらに、数学的帰納法により S(M) = M−2 も示される。