質問
0からU-1までのキーを持つ固定された整数全体集合（universe）が与えられたとき、挿入、削除、所属判定、最小値、最大値、先行元（predecessor）、後続元（successor）をサポートするvan Emde Boas木（vEB木）を実装してください。highとlowの分解、サマリー構造、空クラスタの処理、および操作がO(log U)ではなくO(log log U)になる理由を説明してください。
面接官が見ているポイント
- vEB木が固定された整数全体集合とビット演算を前提としており、任意のオブジェクトに対する比較ベースの木を直接置き換えるものではないことを理解しているか。
- クラスタのインデックスとオフセットを正しく計算し、空でないクラスタをサマリー（summary）に正しく反映・維持できるか。
- 空の木、要素が1つのみの状態（singleton）、境界キー、最小値の削除、およびクラスタが空になった後のクリーンアップを適切に処理できるか。
- 理論上の計算量とO(U)の空間コストを提示し、y-fast trie、ソート済み配列、または通常の平衡探索木が望ましいケースを挙げられるか。
模範解答
Uをビット幅wの2の累乗とします。各vEBノードはサイズuの部分全体集合を保持し、キーを上位のクラスタインデックス（high）と下位のオフセット（low）に分割します。標準的な再帰定義では、両方の半分が約半分のビットを使用するため、ノードは約sqrt(u)個のクラスタを持ちます。各クラスタはサイズsqrt(u)の別のvEB木であり、サイズsqrt(u)のサマリーがどのクラスタが空でないかを記録します。
ノードにはminとmaxも格納され、一般的な操作で葉まで再帰しないようにします。最初の要素を挿入すると両方の値が設定されます。その後の挿入では、より小さいキーをminにスワップし、古いminを該当するクラスタに挿入します。削除では、minまたはmaxの削除を処理し、サマリーを介して次の空でないクラスタを見つけ、クラスタが空になった際にはサマリーからそのクラスタを削除する必要があります。
漸化式はT(u)=T(sqrt(u))+O(1)です。平方根を繰り返し取ることで各レベルで指数が半減するため、深さはO(log log U)になります。素朴なレイアウトでは、再帰ノード全体でのクラスタポインタとサマリーによってO(U)の空間を消費します。疎なレイアウト（sparse layouts）を使用することで定数倍は削減できますが、それ単体では全体集合への依存性を完全に排除することはできません。
実装の概要
以下の疑似コードでは、分解と再結合にhigh、low、indexを使用し、メモリプールや引数の検証は省略しています。
high(x, bits) = x >> ceil(bits / 2)
low(x, bits) = x & ((1 << floor(bits / 2)) - 1)
index(h, l, bits) = (h << floor(bits / 2)) | l
insert(v, x):
if v.min is empty:
v.min = x; v.max = x; return
if x < v.min:
swap(x, v.min)
if v.bits > 1:
h = high(x, v.bits); l = low(x, v.bits)
if v.cluster[h].min is empty:
insert(v.summary, h)
insert(v.cluster[h], l)
if x > v.max:
v.max = x
successor(v, x):
if v.min is empty or x >= v.max: return empty
if v.bits == 1:
return v.max if v.max > x else empty
if x < v.min: return v.min
h = high(x, v.bits); l = low(x, v.bits)
c = v.cluster[h]
if c is not empty and l < c.max:
return index(h, successor(c, l), v.bits)
next_h = successor(v.summary, h)
if next_h is empty: return empty
return index(next_h, v.cluster[next_h].min, v.bits)実際の削除の実装では、対称的な空クラスタの規則を維持する必要があります。葉ノードは、オブジェクトを再帰的に割り当てる代わりに、小さなビットマップや2つの値を使用できます。まずビット幅を固定し、ランダムな操作シーケンスを実行して順序付きセット（ordered set）と比較することで、先行元および後続元の結果が一致することを確認します。
よくある落とし穴
- Uを要素数nとして扱い、すべての操作がO(log log n)であると主張すること。パラメータは全体集合のサイズUです。
- Uが2の累乗でない場合の端数処理を無視し、high、low、indexが逆操作の関係を保てなくなること。
- 所属判定や最小値は実装しているものの、削除後に空になったクラスタをサマリーから削除し忘れること。
- O(U)の空間コスト、キャッシュ局所性、および実際のキー分布を無視して、vEB木が常に赤黒木より高速であると思い込むこと。
- 全体集合の境界や空の表現を明記せずに、サマリーに同じ再帰構造を与えてしまうこと。
計算量のトレードオフ
マシンワードの整数、既知の全体集合、そして先行元・後続元を中心としたワークロードにおいて、O(log log U)は理論上非常に魅力的です。Uがワード範囲に近いものの集合が疎である場合、素朴なレイアウトではメモリを浪費します。x-fast trieやy-fast trieは、ハッシュ処理、ランダム性、または実装の複雑さと引き換えに、空間をよりnに依存する形にします。
通常の平衡木は、O(log n)の操作、O(n)の空間、そしてよりシンプルなイテレータセマンティクスを提供します。ソート済み配列は静的な集合やバッチクエリに適しています。面接では、最速の漸近的限界のみを答えるのではなく、キーの定義域、更新の比率、メモリ予算、保守性に基づいて選択してください。
境界の分解をテストするために、Uを2、4、16、および2の累乗以外の全体集合から始めます。ランダムな挿入、削除、クエリのシーケンスを生成し、最小値、最大値、所属判定、先行元、後続元を言語の順序付きセットと比較します。また、重複した挿入、存在しないキーの削除、最後のキーの削除、最小値や最大値の連続削除も網羅してください。
出典
- MIT OpenCourseWare van Emde Boas Trees 講義：再帰的クラスタ、サマリー、および操作の導出。
- カーネギーメロン大学 大学院アルゴリズム講義 第7回：O(log log U)の漸化式分析と実装の詳細。
- Springerの先行元探索サーベイ：独自のvan Emde Boasの論文と先行元問題の背景。
フォローアップ質問
なぜサマリー構造が必要なのですか？
現在のクラスタにこれ以上大きな要素がない場合、木は次の空でないクラスタを素早く見つける必要があります。サマリーはクラスタを線形探索する代わりに、「どのクラスタが空でないか」を別の先行元・後続元問題に変換します。
なぜminとmaxはクラスタの外に保持できるのですか？
minとmaxを別々に保持することで、空の木や単一要素の操作がO(1)時間になり、再帰呼び出しを減らすことができます。挿入時はより小さい値をminにスワップし、削除時はサマリーを介して代替となる極値を見つけて不変条件を回復します。
Uが2の累乗でない場合はどうなりますか？
すべての有効なキーをカバーする2の累乗の全体集合へと切り上げ、元の範囲外のキーを拒否します。あるいは、端数処理されたクラスタ境界を実装しますが、high、low、indexが互いに逆操作の関係を維持し、計算量が維持されることを証明する必要があります。
O(U)の空間を削減するにはどうすればよいですか？
疎クラスタ、x-fast trie、またはy-fast trieを使用します。単にビッグオー記法を比較するだけでなく、ハッシュの衝突、ランダム性、イテレータのセマンティクス、定数倍の要素についても説明してください。
どのような場合にvEB木を避けるべきですか？
キーの定義域が非常に大きく疎である場合、全体集合を固定できない場合、一般的な比較関数（comparator）が必要な場合、あるいは理論的な限界よりも成熟したイテレータの挙動が重視される場合は、平衡木やB木を使用してください。