Van Emde Boas木
log m が整数だという仮定は実際には不要である。 x M {\displaystyle x{\sqrt {M}}} と x mod M {\displaystyle x{\bmod {\sqrt {M}}}} の計算は、上位 ⌈m/2⌉ ビットと下位 ⌊m/2⌋ ビットを取る操作で置き換えられる。現実の計算機では、割り算や剰余の計算よりこれはずっと高速である。
実用的な実装、特にビットシフトや最上位の 0 ビットを求める命令を持つマシンでは、m がワードサイズやその小さな倍数に達したら、データの持ち方をビット配列に変更することで、パフォーマンスを向上できる。ワードサイズの値の操作は全て定数時間で行えるので、漸近的な性能には影響しないが、大部分のポインタの保存と参照を省くことができ、大幅な時間計算量と空間計算量の削減が実現できる。
明らかな vEB 木の最適化として考えられるのは、空の部分木を省くことである。必要になるまで部分木が作られないので、多くの要素を含む場合、これで vEB 木のサイズは劇的に小さくなる。最初は、要素が追加されるたびに、合計 m/2 個のポインタを含む log(m) 個の新しい木が作られる。
vEB 木からの削除は最も複雑な操作である。
vEB 木 T からの値 x の削除 Delete(T, x) は次のように実現できる:
もT.min = T.max = x なら、x が唯一の要素であるから、木は空になり、T.min = M と T.max = −1 とする。
x == T.min なら vEB 木で 2 番目に小さい値 y を探してそれを削除し、T.min = y とする。y は T.children[T.aux.min].min を計算すれば求められるから、O(1) で求まって、あとは y を部分木から削除すればよいだけである。
x≠T.minかつ x≠T.max なら、T.children[i] から x を削除する。
もし x == T.max なら、vEB 木で 2 番目に大きい値 y を探して、T.max=y としなければならない。前の場合と同じように x を削除した後、2 番目に大きい値は T.min か T.children[T.aux.max].max であるから、O(1) で計算できる。
上のすべての場合において、削除によって T.children[i] が空になったら、i を T.aux から削除する。
この操作場合でも、挿入の場合と同じように、ひとつしか要素のない vEB 木からの削除が定数時間で行えることが重要である。2 番目の再帰呼び出しは、x が対応する部分木の唯一の要素だった時にのみ発生する。