1. 問題と背景
検索、挿入、削除、およびキーによる随時の分割（split）とそれに続く統合（merge）をサポートする動的な順序付き集合を管理します。treap を実装してください。各ノードは key に関する二分探索木（BST）の不変条件と、ランダムな priority に関する最大ヒープの不変条件を満たします。まずはキーが一意であると仮定し、その後に重複の扱いを説明してください。
2. 面接官が見ているポイント
- BST の不変条件とヒープの不変条件がそれぞれ何を提供するのかを説明できるか。
- 回転操作を暗記するだけでなく、
splitとmergeから insert や erase を合成できるか。 O(log n)が期待値（expected）であること、および乱数の品質や優先度の衝突が木の形状に影響を与えることを述べられるか。- 空の子ノードの処理や正しい更新順序を守りつつ、部分木のサイズや集約値を維持できるか。
3. 事前に確認すべき質問
- キーは一意ですか？重複が許可される場合、等しいキーを一貫して片側に配置するか、
(key, id)を複合キーとして使用します。 - 優先度は呼び出し側から渡されますか、それとも内部で生成されますか？内部生成の場合は、乱数ソース、衝突ポリシー、および再現可能なテスト用シードが必要です。
splitは境界キーを左側に配置しますか、それとも厳密な未満（less-than）での分割が必要ですか？これにより、挿入や範囲クエリのコードが変わります。- k 番目の順序統計量、範囲の合計値、または暗黙のシーケンス（implicit sequence）が必要ですか？その場合、変更操作のたびに部分木のメタデータを更新する必要があります。
4. 30秒の回答フレームワーク
「キーによる BST の順序と、ランダムな優先度による最大ヒープの順序を維持します。中核となる操作は、境界以下のキーとそれより大きいキーを返す split(T, key) と、L 内のすべてのキーが R 内のすべてのキー以下であると仮定して優先度の高い方のルートを選択する merge(L, R) です。insert は新しいキーの周囲で split して再 merge し、erase は対象ノードの子同士を merge します。再帰から戻るたびにサイズを更新します。高さと操作の計算量はワーストケースではなく期待値 O(log n) であるため、本番環境のコードでは再現可能なテスト、深さの監視、または決定論的な計算量保証を持つ木構造が必要です。」
5. ステップごとの論理展開
まず不変条件を定めます。すべてのノードにおいて、左の子のキーはそのノードのキー以下、右の子のキーはそれより大きく、優先度は両方の子の優先度以上となります。この記事では「等しいキーは左へ配置する」を採用します。複合の (key, uniqueId) を使用することも明確なポリシーの1つです。
次に split を実装します。ルートのキーが境界以下の場合、ルートと左部分木は左側の結果に属するため、右の子へと再帰します。そうでない場合は、右側の結果を得るために左の子へと再帰します。返された子を再接続し、サイズを更新します。訪問されるのはルートから葉への1つのパスのみです。
3番目に merge を実装します。まず空の木を処理します。左のルートの方が高い優先度を持つ場合、それをルートとして維持し、その右の子と右の木をマージします。そうでない場合は、右のルートを維持し、左の木とその左の子をマージします。「すべての左キーがすべての右キー以下である」という前提条件により、BST の順序が保たれます。
4番目に操作を合成します。insert の場合は split(root, key) を行い、その後に merge(merge(left, node), right) を実行します。erase の場合は、対象を merge(node.left, node.right) に置き換えます。search はキーに従って下降するため、split を必要としません。サイズを保持している場合は、split、merge、insert、erase のすべての操作後に size = 1 + size(left) + size(right) を実行します。
5番目に計算量と失敗時のリスクを検討します。ランダムな優先度により、木の形状はランダムに構築された BST と同等になり、期待計算量 O(log n) の操作が実現します。CP-Algorithms には、期待値として対数時間の split、merge、挿入、削除が記載されています。単調に近い優先度が与えられると O(n) の木が生成される可能性があるため、テストでは固定シードを使用し、深さを監視するか、最悪計算量の保証が必須な場合は AVL 木や赤黒木を選択します。
6. 質の高い模範解答
「まず重複キーのセマンティクスを合意した上で、2つの基本操作を実装します。split は境界を基準に左右の木を返し、一方の子を再帰的に分割してルートを再接続します。merge はすべての左キーが右キー以下であると仮定し、より高い優先度のルートを選択します。insert は split を行ってその結果の間に新しいノードを配置し、erase は対象ノードの子同士をマージします。部分木サイズを更新することで、k 番目の要素の選択も可能になります。ランダムな優先度による高さの保証はワーストケースではなく期待値 O(log n) であるため、空の木、重複、長い操作トレースに対して固定シードでテストし、深さを監視します。決定論的な保証が重要な場合は赤黒木を選択します。」
7. よくある間違い
- 間違い → BST の順序のみを維持する → ソート済みの挿入によってリンクリストになってしまう → 優先度のヒープ不変条件も維持する。
- 間違い → キーの範囲を確認せずに merge を行う → 探索が誤ったパスを辿る → 左のキーが右のキー以下であることを明記・徹底する。
- 間違い → split 後に部分木のサイズの更新を忘れる → k 番目の選択や範囲統計が狂う → 子を再接続した直後にメタデータを集約・更新する。
- 間違い → 期待値
O(log n)を最悪ケースの保証として扱う → 悪意ある優先度によって深い木が作られる可能性がある → 深さを監視するか、AVL木/赤黒木を使用する。 - 間違い → search、erase、split の間で重複ポリシーが一貫していない → 等しいキーが誤った部分木に入ってしまう → 複合キーを使用するか、1つの境界ルールを徹底する。
8. フォローアップ質問
k 番目に小さい要素をどのようにサポートしますか？
各ノードに部分木のサイズを保持します。木を下降しながら k と左部分木のサイズを比較します。split、merge、挿入、削除のたびにサイズを更新してください。そうしないとクエリの結果が不正確になります。
treap で暗黙のシーケンス（implicit sequence）をどのように表現できますか？
明示的なキーを保存しません。ノードの位置は、その左部分木のサイズと祖先からの寄与によって定義します。位置によって split し、再 merge することで、挿入、削除、範囲集約をサポートできます。遅延伝播フラグ（lazy flags）を使用すれば、範囲の反転や加算も処理できます。
treap の使用を避けるべきケースはどのような場合ですか？
厳密な最悪計算量 O(log n)、制御された乱数性、または実績のある並行実装が必要な場合は、AVL 木、赤黒木、またはデータベースのインデックスを選択してください。treap はその保証を犠牲にする代わりに、短いコード量と柔軟な split/merge の構成力を提供します。