1
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

平衡二分木入門 : Splay Tree ~激強データ構造筆頭(個人の感想です)~

Last updated at Posted at 2024-12-16

まえがき

この記事は投稿者(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$ である。
以上の順序に従って数列 $a$ の要素を左から順に頂点に割り振ることで、二分探索木を数列と対応させることができます。なお、この記事では平衡二分木の使い道として、MultiSet Ver. と 数列 Ver. の $2$ 種類を紹介します。

SplayTree.001.jpeg

まずは二分木を数列と対応させた形で解説していきます。ここでは、平衡二分木の頂点はを持つものとし、その値が数列の要素と対応します。


木の平衡

二分探索木では、アクセスしたい頂点を根から探索します。このとき、木の深さが大きいと探索に時間がかかってしまいます。任意の葉頂点の深さの差が小さいとき、二分木が平衡であるといい、そのような二分木を平衡二分木と言います。

SplayTree.002.jpeg


Splay

唐突ですが、「頂点にアクセスするたびに、その頂点が新たに木の根になるまで、木の順序を崩さないように回転する」操作を導入します。

SplayTree.003.jpeg

意味がわからないと思いいますが、より具体的には、アクセスした頂点に対して以下の回転 (rotate) を行います。回転の方向は C が親 (P) から見て左右のどちらにあるかで異なります。また、C は P の親からの辺を引き継ぎます。

SplayTree.004.jpeg

回転を繰り返すことで、アクセスした頂点はいずれ木の根になります。ここで更に以下の $2$ 種類の回転を導入することで、なぜかだんだん木が平衡になります。

SplayTree.005.jpeg

具体的には、自分 (アクセスした頂点) ,親,親の親 の位置関係で以下のように場合分けして回転を行います。

  • 親の親が存在しない場合、自分を $1$ 回 rotate する。
  • (自分-親),(親-親の親) をつなぐ $2$ 本の辺が同じ向きの場合、親を rotate してから自分自身を rotate する。
  • そうでない場合、自分を $2$ 回 rotate する。
この操作を、アクセスした頂点が木の根になるまで繰り返します。これを splay操作 と言います。

なんでこれでだんだん平衡になるのか

しりません。TODO にしておきます。


集約と遅延評価

大体同じなので、より詳細な説明はセグ木の記事を参照してください。

集約

自身以下の部分木の要素の集約を保持することで、区間取得クエリに回答できます。要素アクセスのことを考えると、部分木に属する頂点の個数の集約は必須です。

SplayTree.006.jpeg

遅延評価 ( lazy )

木を変形して、ターゲットの区間をうまくカバーするように部分木を取り出すことで、部分木の要素を代表してその根に評価を遅延させることができます。そうすることで、区間更新や区間反転クエリに回答できます。

SplayTree.007.jpeg

評価 ( eval )

評価 (作用) が遅延しているノードを見たら、何よりもまず遅延評価を評価して解消します。評価した頂点から下のノードは未評価のままなので、評価後は子ノードに遅延評価を伝播させます。

SplayTree.008.jpeg

集約の計算 ( update )

あるノードの集約は「左右のノードの集約 と 自分自身が持つ値 のマージ」です。ただし、左右のノードには遅延評価があるかもしれないので、先に左右のノードを評価 (eval) してから自身の集約を計算します。

SplayTree.009.jpeg


rotate および 集約/遅延評価 の計算

rotate を行うと、辺の構成の変化によって頂点の 集約/遅延評価 が別のものにかかることなります。よって、rotate を行う前に少なくとも rotate による影響がある範囲内の遅延評価は解消し、また回転後は集約の値を再計算する必要があります。

以下の例は代表的な遅延評価の $1$ 例である区間反転を持つ場合です。

SplayTree.010.jpeg

遅延評価は上から伝播するので、P $\rightarrow$ C の順に評価(eval) を呼び出して遅延評価を解消します。

SplayTree.011.jpeg

rotate の影響範囲内の遅延評価は解消されたので、C-P を回転し、その後集約を再計算します。

SplayTree.012.jpeg

集約は部分木 (下からの順) に沿って更新するので、P $\rightarrow$ C の順で集約の計算(update) を呼び出します。


要素アクセス

要素アクセスとして、以下を定義します。

  • $\mathrm{get}(x) := $ 左から $x$ 番目のノードにアクセス

各頂点に自身以下の部分木に含まれるノードの個数を集約させておくことで、$\mathrm{get}(x) $ で向かうべき方向を特定することができます。例えば以下は 0-index で左から $3$ 番目のノードにアクセスする様子です。

SplayTree.013.jpeg

アクセス後は splay するのを忘れないでください。


列操作 (split/merge)

split と merge をベースに列操作を行います。

まずは $\mathrm{split}(x)$ を以下で定義します。

  • $\mathrm{split}(x) := $ Splay Tree を、左から $x$ 番目のノード以降と、それより前で $2$ 分割する。
$x$ 番目のノードを根としたとき、左の子につながる辺を cut します。このとき、分割された $2$ つの Splay Tree の根をどこかに管理しておく必要があります。

SplayTree.014.jpeg

また、split の逆の操作として $\mathrm{merge}(r1,r2)$ を定義します。

  • $\mathrm{merge}(r1,r2) := $ $r1,r2$ を根とする Splay Tree をこの順に結合する。
$r2$ の最左の頂点を splay し、その頂点の左の子として $r1$ を link します。

SplayTree.015.jpeg

split と merge は逆の操作です。split したものを merge して元に戻すとき、このことを利用して split は右から、merge は左から行うことで定数倍の改善が見込めます。


部分木の取得

split によって左から $l$ 番目以上 $r$ 番目未満の区間のノードを一括で取得できます。具体的には、$\mathrm{split}(r) \rightarrow \mathrm{split}(l)$ を実行することで、半開区間 $[l,r)$ の要素からなる Splay Tree を取り出し、その根を管理します。

例えば半開区間 $[2,7)$ は以下のように管理できます。

SplayTree.016.jpeg

根 $C$ の集約を見ることで、半開区間 $[2,7)$ 内の要素の集約を取得できます。また、根 $C$ に遅延評価を載せて、$L,C,R$ をこの順に merge することで、$C$ の区間の部分のみを区間更新することができます。

以下は $[2,7)$ を区間反転する場合です。

SplayTree.017.jpeg


削除

splitで $x$ 番目のノードと、その左右の木 $L,R$ を切り離して、$L,R$ のみを merge することで、木から $x$ 番目のノードを削除できます。

SplayTree.018.jpeg


挿入

$x$ 番目で split したものを $L,R$ として、$L$,「要素 $V$ を持つ新たなノード : $Nd$」,$R$ を順に merge することで、$x$ 番目に $V$ を挿入できます。

SplayTree.019.jpeg


要素の検索 (読み飛ばしても 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$ つの連結成分を管理している前提が必要 (削除が記録されたノードは例外)。

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 として扱う平衡二分木も、当然先で紹介した操作を行うことができます。

SplayTree.020.jpeg

MultiSet 型の平衡二分木は特殊なケースの数列 (ソートされた数列) に対応しているので、先に挙げた操作に加えてさらにいくつかの操作を行うことができます。

領域の分割

  • $\mathrm{lower\_bound}\prime(x) := $ $x$ 以上の要素のうち、最も左のものを検索する。
  • $\mathrm{upper\_bound}\prime(x) := $ $x$ より大きいの要素のうち、最も左のものを検索する。
要素アクセスと同様に、根から左右の子を調べながら降りて探索していきます。左右の子頂点が持つ値と $x$ の大小を比較して降りるべき方向を決めます。

要素の位置に対して、上記の $x$ に関する条件に単調性があることに注目すると、 $\mathrm{lower\_bound}\prime(x)$ や $\mathrm{upper\_bound}\prime(x)$ で求めるものはいずれも、$x$ に関する条件で領域を二分したとき、その境界の直後であることがわかります。

以下は $\mathrm{lower\_bound}\prime(7)$ の様子です。

SplayTree.021.jpeg

ただし木上での移動は、必ずしも二分される領域の右側だけで収まるとは限りません。探索過程によっては答えとなるノードよりも左の領域で探索が終了してしまう場合があります。例えば自分の実装では $\mathrm{lower\_bound}\prime(5)$ は以下のようになります。

SplayTree.022.jpeg

本来取得したいノードの左、つまり二分された領域の境界の直前で探索が終了してしまっていることがわかります。最後にもう一度根まで戻ってから右に一つずらせば解決しますが、定数倍の問題で好ましくはありません。

そこで、$\mathrm{lower\_bound}\prime(x)$ と $\mathrm{upper\_bound}\prime(x)$ を少し変えて、以下を定義することにします。

  • $\mathrm{lower\_bound}(x) := $ 多重集合のうち $x$ 未満の要素数
  • $\mathrm{upper\_bound}(x) := $ 多重集合のうち $x$ 以下の要素数
これらは、$\mathrm{lower\_bound}\prime(x)$ または $\mathrm{upper\_bound}\prime(x)$ で到達した頂点を splay して根にした後、その頂点の左側の部分木サイズを見ることで計算可能です。ただし先述のように最終的に到達した頂点が境界の直前の場合、結果に $+1$ したものを返すようにします。到達した頂点が境界の直前か直後かは、到達した頂点が持つ要素と $x$ を比較することで容易に判定することができます。

頂点に実際にアクセスする場合は結局一つ右にずらす場合がありますが、条件を満たす要素数、すなわち MultiSet 内での位置だけ欲しい場合に無駄な操作を省略できるのでこのように定義しました。


要素の発見,削除

$\mathrm{lower\_bound}(x)$ から、以下の機能を追加できます。

  • $\mathrm{find}(x) := $ $x$ が小さい方から何番目の要素かを返す。存在しなければ $-1$ を返すなど。
  • $\mathrm{erase}(x) := $ $x$ を多重集合から $1$ つ削除する。
これだけで C++ の std::set の完全上位互換と言えますし、集約などを活用することでさらに機能を追加できます。例えば頂点にペア $(k,v)$ を持たせて、$k$ の範囲が $[l,r)$ 以内の要素の $v$ の総和や Min/Max を取ったりもできます (要素の順序は $(k,v)$ の辞書順)。

いかがでしたか

いかがでしたか

1
1
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
1
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?