課題とユースケース
インターバルツリーは動的な時間範囲、予約、リソースの占有状況に適しています。中核となるアイデアは、下限終端点で順序付けられた平衡木に各部分木の最大上限終端点を拡張（augmentation）として保持させ、探索不要な枝をスキップすることです。
面接官が評価するポイント
- 閉区間の境界と重複の判定が正しいか。
maxEndが正確に定義され、維持されているか。- すべてのノードを走査するのではなく、拡張情報によって枝刈りが行われているか。
- 挿入、削除、回転時に拡張情報が更新されているか。
- 重複、空のツリー、存在しない要素の削除が処理されているか。
- 計算量に報告される区間数が考慮されているか。
回答前の確認事項
- 区間は閉区間、開区間、半開区間のいずれですか？
- 終端点は整数、浮動小数点数、タイムスタンプのいずれですか？
- 重複区間は許可されますか？また、削除はIDまたは終端点のどちらを使用しますか？
- クエリは重複するすべての区間を返す必要がありますか、それとも1つだけですか？
- オンラインでの挿入、削除、自己平衡化は必須ですか？
- 結果は下限終端点でソートされている必要がありますか？
30秒回答フレームワーク
「下限終端点をキーとする平衡木を使用し、上限終端点に加えて部分木の最大値 maxEnd を保持します。クエリは現在のノードとの重複を報告し、左部分木の maxEnd がクエリの下限に到達可能な場合にのみ左部分木へ進み、現在のノードの下限終端点がクエリの上限以内である限りにおいてのみ右部分木へ進みます。挿入と削除は平衡木の操作を使用し、パス上の maxEnd を更新し、回転後に影響を受けたノードを再計算します。」
ステップバイステップの詳細解説
ステップ 1: 重複を定義する。 閉区間 [a,b] と [c,d] は、a <= d かつ c <= b である場合に正確に重複します。まず a > b を除外します。
ステップ 2: ノードを定義する。 low、high、一意のID、子ノード、および maxEnd を保持します。等しい終端点でも区別できるように (low, id) で順序付けします。
ステップ 3: クエリを枝刈りする。 重複する場合は現在のノードを報告します。left.maxEnd >= query.low の場合にのみ左へ再帰し、現在の low <= query.high の場合にのみ右へ再帰します。
ステップ 4: 拡張情報を維持する。 maxEnd はノードの high と両方の子の値の最大値です。更新や回転の後は影響を受けたパスのみを再計算します。
ステップ 5: 安全に削除する。 IDで検索し、平衡木の削除を実行し、置換パスから上方に向かって maxEnd を更新します。IDが存在しない場合は明示的な結果を返します。
ステップ 6: 境界値をテストする。 接している終端点、包含関係、重複、負の値、点区間、空のツリー、およびすべての区間が含まれる出力を網羅します。
ステップ 7: 計算量を述べる。 平衡木の高さは対数です。クエリは報告される区間数 k に対して O(log n + k)、更新は O(log n)、空間計算量は O(n) です。
質の高い模範解答
「(low, id) で順序付けられた赤黒木を使用し、各ノードに high と部分木の maxEnd を保持します。[q1,q2] に対しては、low <= q2 かつ high >= q1 のときに報告します。left.maxEnd >= q1 の場合にのみ左の子へ進み、現在の low <= q2 の場合にのみ右の子へ進みます。挿入と削除ではパス上の最大値を更新し、回転では回転されたノードと親ノードを再計算します。IDにより重複を区別します。閉区間の終端点やすべて一致する出力をテストします。クエリは O(log n + k)、更新は O(log n) です。」
よくあるミス
- 重複判定に
low < q2を使用する → 接している終端点が検出されなくなる → 選択した区間タイプと一致させる。 - 各ノードの
highのみを保持する → 枝刈りが不可能になる → 部分木のmaxEndを維持する。 - 回転後の拡張情報更新をスキップする → 以降のクエリが誤った結果になる → 影響を受けたノードを再計算する。
- クエリを
O(log n)と主張する → 出力コストが抜けている →O(log n + k)と記述する。 - 等しい終端点を上書きする → 削除や出力が不安定になる → 一意のIDまたは複合キーを使用する。
フォローアップ質問と回答
フォローアップ 1: クエリが点のみの場合はどうなりますか？
[x,x] と同様の maxEnd の枝刈りを使用します。終端点が小さな整数で静的な場合は、特化した離散構造を検討します。
フォローアップ 2: なぜリストを走査しないのですか？
区間が多く更新が混在している場合、走査ではすべてのノードを探索することになります。ツリーを使用することで、探索を対数パスと報告される出力分のみに制限できます。
フォローアップ 3: なぜ回転後も maxEnd が維持されるのですか？
変更されるのは局所的な部分木のみであるため、影響を受けたノードをボトムアップで再計算することでフィールドの定義が復元されます。
フォローアップ 4: 重複する区間をどのように削除しますか？
挿入時にIDを割り当て、(low, ID) をキーとし、IDによって削除することで、終端点が等しい他の区間を残します。
フォローアップ 5: 浮動小数点数の終端点はどう扱いますか？
NaN、精度、同値性のセマンティクスを定義します。可能な場合は整数のティックや時間単位に変換します。
フォローアップ 6: ソートされた出力をどのように保証しますか？
通りがけ順（in-order）の走査により下限終端点の順序が得られます。枝刈りによって訪問順序が変わる場合は、収集した後にソートし、追加のコストを明記します。
フォローアップ 7: なぜこの枝刈りは安全なのですか？
左部分木の最大終端点がクエリの下限よりも小さい場合、その部分木のすべての区間は重複するには早すぎる時点で終了するため、スキップしても安全です。