まえがき
この記事は投稿者(NokonoKotlin)の個人サイトの記事から Qiita 用に移植 & 加筆したものです。(この文言は記事が剽窃でないことを周知するためのものであり、個人サイトの宣伝ではないことをあらかじめご了承ください。)
平衡二分木
平衡二分木を書いたら AtCoder 青になれました。ABC の D,E 問題は平衡二分木を使って即答できることも多く、青になってからも D,E の速解きのおかげでレート減少を抑えることができます。多分競技プログラミングで最も活躍できるデータ構造だと思います。
自分のお語り
思えば、初めて自分でちゃんと書いたデータ構造ライブラリは、かつっぱさんの木マスター養成講座で勉強した Splay Tree でした。
二分木
二分木は全ての頂点の子が高々 $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 にしておきます。
集約と遅延評価
大体同じなので、より詳細な説明はセグ木の記事を参照してください。
集約
自身以下の部分木の要素の集約を保持することで、区間取得クエリに回答できます。要素アクセスのことを考えると、部分木に属する頂点の個数の集約は必須です。
遅延評価
自身以下の部分木の要素への作用を自身に遅延させておくことで、区間更新クエリに回答できます。
評価
評価 (作用) が遅延しているノードを見たら、何よりもまず遅延評価を評価します。
集約の計算
あるノードの集約は「左右のノードの集約 と 自分自身が持つ値 のマージ」です。ただし、左右のノードには遅延評価があるかもしれないので、先に左右のノードを評価 (eval) してから自身の集約を計算します。
rotate および 集約/遅延評価 の計算
rotate を行うと、辺の構成の変化によって頂点の 集約/遅延評価 が別のものにかかることなります。よって、rotate を行う前に少なくとも rotate による影響がある範囲内の遅延評価は解消し、また回転後は集約の値を再計算する必要があります。
以下の例は代表的な遅延評価の $1$ 例である区間反転を持つ場合です。
遅延評価は上から伝播するので、P $\rightarrow$ C の順に評価(eval) を呼び出して遅延評価を解消します。
rotate の影響範囲内の遅延評価は解消されたので、C-P を回転し、その後集約を再計算します。
集約は部分木 (下からの順) に沿って更新するので、P $\rightarrow$ C の順で集約の計算(update) を呼び出します。
要素アクセス
左の部分木のサイズを参照しながら根から探索することで、キーの昇順で $i$ 番目の要素にアクセスできます。
以下は $a_x (x = 4) $にアクセスする様子です。
列操作 (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$ を挿入できます。
Set にする。
これまで説明してきた平衡二分木は、頂点を数列の要素に対応させたものでした。ここで、管理する数列 $a$ に以下の制約がついているとき、平衡二分木を順序付き多重集合として使用することができます。
- $i\leq j \rightarrow a_i \leq a_j$
Set 型の平衡二分木は特殊なケースの数列 (ソートされた数列) に対応しているので、先に挙げた操作に加えてさらにいくつかの操作を行うことができます。
要素の検索
- $\mathrm{lower\_bound}(x) := $ $x$ 以上の要素のうち、最も左のものを検索する。
- $\mathrm{upper\_bound}(x) := $ $x$ より大きいの要素のうち、最も左のものを検索する。
以下は $\mathrm{lower\_bound}(7)$ の様子です。
また $\mathrm{lower\_bound}(x),\mathrm{upper\_bound}(x)$ について、以下が成り立ちます。
- 多重集合のうち $x$ 未満の要素数は、$\mathrm{lower\_bound}(x)$ で到達した頂点を splay した後の左の子の部分木サイズである。
- 多重集合のうち $x$ 以下の要素数は、$\mathrm{upper\_bound}(x)$ で到達した頂点を splay した後の左の子の部分木サイズである。
これらの結果から、以下の機能を追加できます。
- $\mathrm{find}(x) := $ $x$ が小さい方から何番目の要素かを返す。存在しなければ $-1$ を返すなど。
- $\mathrm{erase}(x) := $ $x$ を多重集合から $1$ つ削除する。
いかがでしたか？
いかがでしたか？