77. C# で MultiSet を実装する（大枠の話と列挙アルゴリズムについて）

ここで言う MultiSet とは C++ の multiset を模したデータ構造です。C# に標準で存在しないため、競技プログラミングなどで利用したい場合は自作する必要があります。

MultiSet は端的に言うと、順序を保ったまま高速に要素を追加・削除・検索可能なリストです。順序を保つことから、二分探索によって検索を対数時間で行えます。

対数時間がどのくらい速いのか、というイメージは以下の記事を参照してください。

このデータ構造では、以下の性質を満たす必要があります。

LowerBound / UpperBound でイテレータを返すことによって、「指定した値を基準にした順序」を高速に見ることができます。指定した値を対数時間で見つけて、そこからは線形時間でアクセスするイメージです。

これにより、例えば以下のような問題を解くことが可能になります。

要素の検索を対数時間で行いたいことから、二分探索木を内部で持つと良いです。二分探索木は、以下のような性質を持つ木です。

たとえば、以下のような木が二分探索木の性質を満たしています。

単純な二分探索木は最悪計算量が $O(N)$ になります。
たとえば、以下のようにソート済みの値が順に追加された場合、一方向にしか枝が伸びず、ただの片方向リストと何ら変わりない構造となってしまいます。

そこで、データ数 $N$ に対して深さの最大値がなるべく $\log N$ に近付くよう、「バランスの良い木」を維持する平衡二分探索木というデータ構造が採用されます。

平衡二分探索木にはAVL木・赤黒木など様々な実装が知られていますが、今回の記事では詳細を説明しません。なお、AVL木については以下の記事が分かりやすいと思います。今回実装する MultiSet も、AVL木を利用します。

今回は、データをAVL木で保持した上で、列挙（GetEnumerator）と二分探索（LowerBound / UpperBound）を MultiSet で実装します。

深さ優先探索の応用で昇順列挙が可能になります。

イメージとしては、左・真ん中・右の順で頂点を展開していく、という感じです。

二分探索フェーズとイテレータを返す（列挙）フェーズに分かれており、やや難解です。

空のスタックを用意して、「確認中の頂点」を根とする
「確認中の頂点」が null なら終了
「確認中の頂点」の値について、LowerBoundなら「指定値以上」、UpperBoundなら「指定値より大きい」か比較する。
1. （条件を満たす場合）スタックに「確認中の頂点」を追加し、「確認中の頂点」を左の子に変更して 2. へ
2. （条件を満たさない場合）「確認中の頂点」を右の子に変更して 2. へ

二分探索フェーズでは、毎ループ木を掘っていくことになるので最悪計算量は $O(\log N)$ となります。探索過程で現れた「条件を満たす頂点」がスタックに追加されます。

「条件を満たす場合」の処理の心は、「この頂点は条件を満たすが、これより小さくて条件を満たす値があるかもしれない」ということです。二分探索木の性質から、現在見ている値より小さい値が存在する場合、必ず左の子孫にいます。

「条件を満たさない場合」の処理については、「この頂点は条件を満たさないが、これ以上で条件を満たす値があるかもしれない」です。こちらも二分探索木の性質から言えることです。

たとえば、先ほど例に出した二分探索木で LowerBound(4) を実行した場合、以下のような遷移となります。黄色頂点がスタックに追加されて、薄オレンジ頂点は探索過程で「確認中の頂点」になるものです。