まえがき
この記事は投稿者(NokonoKotlin)の個人サイトの記事から Qiita 用に移植 & 加筆したものです。 (この文言は記事が剽窃でないことを周知するためのものであり、個人サイトの宣伝ではないことをあらかじめご了承ください。)
また、この記事と同様の記事を過去に投稿していました。これはその記事のアップデート版です。
自分の語りなど
平衡二分木を書いたら AtCoder 青になれました。ABC の D,E 問題は平衡二分木を使って即答できることも多く、青になってからも D,E の速解きのおかげでレート減少を抑えることができます。
ライブラリも こちらの Qiita 記事 で公開しています。(もう一つ追加予定)。平衡二分木が具体的にどう役に立つのかは、ライブラリの記事の方で説明しようと思います。
二分木
二分木は全ての頂点の子が高々 $2$ である根付き木です。二分木の頂点同士の関係が以下の順序 ($\leq$) を満たすとき、この二分木を二分探索木と言います。
- 「異なる頂点 $a,b$ に対して $a\leq b$」$\leftrightarrow$「頂点 $a$ が頂点 $b$ より左の頂点である」
- 任意の頂点 $x$ について以下が成り立つ。
- $x$ の左の子の部分木から任意に頂点 $y$ を選んだとき、$x,y$ の順序は $y\leq x$ である。
- $x$ の右の子の部分木から任意に頂点 $y$ を選んだとき、$x,y$ の順序は $x\leq y$ である。
まずは二分木を数列と対応させた形で解説していきます。ここでは、平衡二分木の頂点は値を持つものとし、その値が数列の要素と対応します。
木の平衡
二分探索木では、アクセスしたい頂点を根から探索します。このとき、木の深さが大きいと探索に時間がかかってしまいます。任意の葉頂点の深さの差が小さいとき、二分木が平衡であるといい、そのような二分木を平衡二分木と言います。
Splay
唐突ですが、「頂点にアクセスするたびに、その頂点が新たに木の根になるまで、木の順序を崩さないように回転する」操作を導入します。
意味がわからないと思いいますが、より具体的には、アクセスした頂点に対して以下の回転 (rotate) を行います。回転の方向は C が親 (P) から見て左右のどちらにあるかで異なります。また、C は P の親からの辺を引き継ぎます。
回転を繰り返すことで、アクセスした頂点はいずれ木の根になります。ここで更に以下の $2$ 種類の回転を導入することで、なぜかだんだん木が平衡になります。
具体的には、自分 (アクセスした頂点) ,親,親の親 の位置関係で以下のように場合分けして回転を行います。
- 親の親が存在しない場合、自分を $1$ 回 rotate する。
- (自分-親),(親-親の親) をつなぐ $2$ 本の辺が同じ向きの場合、親を rotate してから自分自身を rotate する。
- そうでない場合、自分を $2$ 回 rotate する。
なんでこれでだんだん平衡になるのか
しりません。TODO にしておきます。
集約と遅延評価
大体同じなので、より詳細な説明はセグ木の記事を参照してください。
集約
自身以下の部分木の要素の集約を保持することで、区間取得クエリに回答できます。要素アクセスのことを考えると、部分木に属する頂点の個数の集約は必須です。
遅延評価 ( lazy )
木を変形して、ターゲットの区間をうまくカバーするように部分木を取り出すことで、部分木の要素を代表してその根に評価を遅延させることができます。そうすることで、区間更新や区間反転クエリに回答できます。
評価 ( eval )
評価 (作用) が遅延しているノードを見たら、何よりもまず遅延評価を評価して解消します。評価した頂点から下のノードは未評価のままなので、評価後は子ノードに遅延評価を伝播させます。
集約の計算 ( update )
あるノードの集約は「左右のノードの集約 と 自分自身が持つ値 のマージ」です。ただし、左右のノードには遅延評価があるかもしれないので、先に左右のノードを評価 (eval) してから自身の集約を計算します。
rotate および 集約/遅延評価 の計算
rotate を行うと、辺の構成の変化によって頂点の 集約/遅延評価 が別のものにかかることなります。よって、rotate を行う前に少なくとも rotate による影響がある範囲内の遅延評価は解消し、また回転後は集約の値を再計算する必要があります。
以下の例は代表的な遅延評価の $1$ 例である区間反転を持つ場合です。
遅延評価は上から伝播するので、P $\rightarrow$ C の順に評価(eval) を呼び出して遅延評価を解消します。
rotate の影響範囲内の遅延評価は解消されたので、C-P を回転し、その後集約を再計算します。
集約は部分木 (下からの順) に沿って更新するので、P $\rightarrow$ C の順で集約の計算(update) を呼び出します。
要素アクセス
要素アクセスとして、以下を定義します。
- $\mathrm{get}(x) := $ 左から $x$ 番目のノードにアクセス
各頂点に自身以下の部分木に含まれるノードの個数を集約させておくことで、$\mathrm{get}(x) $ で向かうべき方向を特定することができます。例えば以下は 0-index で左から $3$ 番目のノードにアクセスする様子です。
アクセス後は splay するのを忘れないでください。
列操作 (split/merge)
split と merge をベースに列操作を行います。
まずは $\mathrm{split}(x)$ を以下で定義します。
- $\mathrm{split}(x) := $ Splay Tree を、左から $x$ 番目のノード以降と、それより前で $2$ 分割する。
また、split の逆の操作として $\mathrm{merge}(r1,r2)$ を定義します。
- $\mathrm{merge}(r1,r2) := $ $r1,r2$ を根とする Splay Tree をこの順に結合する。
split と merge は逆の操作です。split したものを merge して元に戻すとき、このことを利用して split は右から、merge は左から行うことで定数倍の改善が見込めます。
部分木の取得
split によって左から $l$ 番目以上 $r$ 番目未満の区間のノードを一括で取得できます。具体的には、$\mathrm{split}(r) \rightarrow \mathrm{split}(l)$ を実行することで、半開区間 $[l,r)$ の要素からなる Splay Tree を取り出し、その根を管理します。
例えば半開区間 $[2,7)$ は以下のように管理できます。
根 $C$ の集約を見ることで、半開区間 $[2,7)$ 内の要素の集約を取得できます。また、根 $C$ に遅延評価を載せて、$L,C,R$ をこの順に merge することで、$C$ の区間の部分のみを区間更新することができます。
以下は $[2,7)$ を区間反転する場合です。
削除
splitで $x$ 番目のノードと、その左右の木 $L,R$ を切り離して、$L,R$ のみを merge することで、木から $x$ 番目のノードを削除できます。
挿入
$x$ 番目で split したものを $L,R$ として、$L$,「要素 $V$ を持つ新たなノード : $Nd$」,$R$ を順に merge することで、$x$ 番目に $V$ を挿入できます。
要素の検索 (読み飛ばしても OK)
もしもあるノードのポインタを持っているなら、そのノードが Splay Tree の左から何番目の要素か (0-index) を特定することができます。具体的には、そのポインタが指すノードを splay し、左の部分木のサイズを返すだけです。例えば、列型の Splay Tree には以下の機能を搭載できます。
-
$\mathrm{find}(x) := $「$a_i = x$」である $i$
- 値が $x$ であるノードへのポインタを、ハッシュテーブルなどで持っておく。
- 区間更新と値の重複に対応していない。
上記の方法はシンプルですが、少し制約が強いのでもう少し工夫をして制約を緩和します。まず、要素の検索では区間更新がある場合の対応は厳しいです。しかし、値の重複に対しては以下のようにして対応できます。
-
$\mathrm{find}(x,c) := $「$a_i = x$」である $i$ を $c$ 種類選んで返す。ただし、選び方は保証しない。
-
値が $x$ であるノードへのポインタを管理する列を、以下のハッシュテーブルで持っておく。
- $\mathrm{ptr}[x] := $ 値に $x$ を持つノードのポインタを管理する列。ただし、管理されているポインタの全てが有効とは限らない。
-
要素の追加,要素の削除,値の変更 に対して、以下の方法で $\mathrm{ptr}$ テーブルと連携させる
- $x$ をもつノードの追加 $\rightarrow$ $\mathrm{ptr}[x]$ にそのノードのポインタを追加する。
- $x$ をもつノードの削除 $\rightarrow$ Splay Tree から削除後、そのノードの実体を破棄する代わりに削除を行った旨をそのノードのメンバに記録しておく。$\mathrm{ptr}[x]$ への操作は行わない (ある種の遅延評価)。
- あるノードが持つ値を $x$ に変更する $\rightarrow$ $\mathrm{ptr}[x]$ にそのノードのポインタを追加する。元々そのノードへのポインタが管理されていた $\mathrm{ptr}$ への操作は行わない (ある種の遅延評価)。
-
$x$ を持つノード $c$ 個の位置の計算を、以下の手続きで行う。
- $\mathrm{ptr}[x]$ の中身を順に見ていく。
-
チェックしたノードが以下のいずれかの場合は invalid なノードであるとして $\mathrm{ptr}[x]$ から削除する。
- ノードがすでに削除済みである。(ノードのメンバを確認して判断)
- ノードの持つ値が $x$ ではない。
- すでに調べたものと同じノードである。(すでに見たノードのポインタをハッシュテーブルなどに記録)
- $c$ 種類列挙した時点で手続きを終了する。
- あたりまえですが $1$ つの Splay Tree クラスは、$1$ つの連結成分を管理している前提が必要 (削除が記録されたノードは例外)。
-
値が $x$ であるノードへのポインタを管理する列を、以下のハッシュテーブルで持っておく。
invalid なノードを初めて見た時に削除することで、要素の削除,値の変更 の操作で $\mathrm{ptr}$ に残された廃棄物をうまく弾くことができます。クエリが $Q$ 回与えられ、うち $\mathrm{find}$ で $C$ 要素列挙する場合の計算量はクエリ全体で $O((C+Q)\log{Q})$ 時間です。
また、$\mathrm{pre}[x]$ を std::vector で実装すると格納したポインタの削除の計算量が良くありません。格納されている要素を前から見れば良いだけなので、代わりに連結リストで実装するなどが良いでしょう。
MultiSet にする
これまで説明してきた平衡二分木は、頂点を数列の要素に対応させたものでした。ここで、管理する数列 $a$ に以下の制約がついているとき、平衡二分木を順序付き多重集合として使用することができます。
- $i\leq j \rightarrow a_i \leq a_j$
MultiSet 型の平衡二分木は特殊なケースの数列 (ソートされた数列) に対応しているので、先に挙げた操作に加えてさらにいくつかの操作を行うことができます。
領域の分割
- $\mathrm{lower\_bound}\prime(x) := $ $x$ 以上の要素のうち、最も左のものを検索する。
- $\mathrm{upper\_bound}\prime(x) := $ $x$ より大きいの要素のうち、最も左のものを検索する。
要素の位置に対して、上記の $x$ に関する条件に単調性があることに注目すると、 $\mathrm{lower\_bound}\prime(x)$ や $\mathrm{upper\_bound}\prime(x)$ で求めるものはいずれも、$x$ に関する条件で領域を二分したとき、その境界の直後であることがわかります。
以下は $\mathrm{lower\_bound}\prime(7)$ の様子です。
ただし木上での移動は、必ずしも二分される領域の右側だけで収まるとは限りません。探索過程によっては答えとなるノードよりも左の領域で探索が終了してしまう場合があります。例えば自分の実装では $\mathrm{lower\_bound}\prime(5)$ は以下のようになります。
本来取得したいノードの左、つまり二分された領域の境界の直前で探索が終了してしまっていることがわかります。最後にもう一度根まで戻ってから右に一つずらせば解決しますが、定数倍の問題で好ましくはありません。
そこで、$\mathrm{lower\_bound}\prime(x)$ と $\mathrm{upper\_bound}\prime(x)$ を少し変えて、以下を定義することにします。
- $\mathrm{lower\_bound}(x) := $ 多重集合のうち $x$ 未満の要素数
- $\mathrm{upper\_bound}(x) := $ 多重集合のうち $x$ 以下の要素数
頂点に実際にアクセスする場合は結局一つ右にずらす場合がありますが、条件を満たす要素数、すなわち MultiSet 内での位置だけ欲しい場合に無駄な操作を省略できるのでこのように定義しました。
要素の発見,削除
$\mathrm{lower\_bound}(x)$ から、以下の機能を追加できます。
- $\mathrm{find}(x) := $ $x$ が小さい方から何番目の要素かを返す。存在しなければ $-1$ を返すなど。
- $\mathrm{erase}(x) := $ $x$ を多重集合から $1$ つ削除する。
いかがでしたか
いかがでしたか