2-3 フィンガーツリー
木を指定した位置で分割するためには、木の各部分に対してその部分が含む要素の数を計算する必要がある。
実際には木の各部分に要素数のキャッシュを追加しておき、再計算しないようにする。
i番目の葉での分割演算は、i番目の葉を含む要素より左の要素からなる木・i番目の葉を含む要素・i番目の葉を含む要素より右の要素からなる木に分割する演算splitTreeAtを使って定義される。
木が要素を1つだけもつときは単純である。ここで、iは0以上、木のサイズ未満とする。
深い木の場合はi番目の葉の位置により場合分けする。まずi番目の葉が左の木や右の木に含まれる場合は、それを分割すればよい。
左右の木の分割は単純にi番目より左の要素と、i番目の要素と、i番目より右の要素に分ければよい。
i番目の葉が中央のより深い木に含まれる場合はひと手間多く必要となる。まず中央の木を分割する。するとi番目の葉を含むNodeが得られる。このNodeをさらに分割すると葉が得られる。
木を一番右の要素とその要素を削除した木に分割する演算popRについて示す。左側を分割する演算popLも同様である。
削除演算はほとんど追加演算の逆である。1つだけ要素を持つ木からの削除は単純である。
深い木に関してもDigitが1以外のときは単純である。例えばの場合は次のようになる。
Digitが1の場合、繰り下がり処理をする。
繰り下がり処理はより深い木が空の場合と空でない場合で場合分けする。空の場合は次のようになる。
ここでtoTreeは空の木にprの要素を順に追加する関数である。
より深い木が空でない場合は次のようになる。
ここでtoDigitはNodeをDigitに変換する関数である。Nodeは2つまたは3つの要素を持つので、それらをTwoまたはThreeに変換する。より深い木の要素はNodeである点に注意。
popRで木を変形する様子を図で示す。ここではpopRとborrowRを合わせて1つの式で書いている。より深い木が空の場合は次のようになる。
より深い木が空でない場合は次のようになる。
追加および削除演算の計算量は式を遅延評価する処理系において償却定数時間である。
以下の図は空の木に右から要素を17個追加し、左から1つずつ削除していく様子である。ただし繰り上がりや繰り下がりの様子がわかりやすいようにDigitは3までに制限してある。
ただしそれらの木の根のみは1から4つの子を持てるように条件を緩和する。これは追加と削除を交互に実行しても処理時間を償却定数時間に保つためである。なお根の分岐数は1から3まででもよい。その場合、計算量のオーダーは変わらないものの木は深くなる。2-3フィンガーツリーをリストとして見た場合、完全二分木に指を導入したときと同じように各要素の木は指数関数的に大きくなる。
2-3フィンガーツリーは形式的には次のように定義される。ここでは記法はHaskellを用いた。
フィンガーツリーは「空の木」「1つだけ要素を持つ木」「深い木」のいずれかである。深い木は列の最初の数要素・最後の数要素・それ以外を保持するフィンガーツリーからなる。Digitは左右の木の根であり、Nodeは分岐数が2または3である平衡木を表す。ただしDigitやNodeは木の深さによって異なる型を持つ。例えばNode Integerは整数を要素としてもつ深さ1の木であり、Node (Node Integer)は整数を要素として持つ深さ2の木である。この型付けは深いフィンガーツリーは左右に持つ木も深くなるという制約を強制し、アルゴリズムを強固で単純にする。左右の木をDigit(数字)と呼んでいるのはフィンガーツリーが数値表現を利用したデータ構造だからである。
列の例では分割する位置iを減少させながら再帰呼び出ししたが、一般化した状態ではモノイドを使うため減算はできない。そこでアキュムレータを用意し、再帰呼び出しに入る前に左側の部分木の値を累積していき、基準値と比べる。
述語pはアキュムレータの初期値では偽となり、木全体に対しては真となる必要がある。列の例では初期値として単位元0を使うので、この制限は「iは0以上、木のサイズ未満である」という制限となる。
以上の条件の元で、一般化した分割演算は次のように書ける。ここでmeasureはノードから値へ変換する関数である。初期値xから始めて値を累積しながらpを満たす要素を探していく。
通常はある要素までは述語は常に偽となり、それより先の要素では述語は常に真となるようにする。しかし述語の真偽は途中で何度も切り替わってもよい。その場合、このアルゴリズムは述語が偽から真に切り変わる要素のうち適当な1つで分割する。