2-3 フィンガーツリー

**2-3フィンガーツリー**(**2-3 finger tree**、または単にfinger tree)とは、列を表す永続データ構造の一種であり、償却定数時間で両端への追加・削除が可能であり、対数時間で連結・分割・挿入が可能である。また、分割演算を変更すると優先度付きキューや探索木などを実装できる。2006年にRalf HinzeとRoss Patersonが発表した。

関数型プログラミング言語などで使われる。Haskellでは、containersパッケージに列に特化した実装のData.Sequenceが含まれ、列に限定しない汎用の実装もfingertreeパッケージとして存在する。Scalaでは標準ライブラリには含まれていないが、scalazなどのライブラリなどで実装されている。その他、様々なプログラミング言語で実装されている。

## 構造
2-3フィンガーツリーは分岐数が2または3である木構造に対して「指(finger)」と呼ばれる構造を導入して作られる。
通常の平衡木では葉に置いた要素にアクセスする際には根から参照を辿る必要があり、要素数に対して対数時間の計算量が必要となる。しかし多くの場合、頻繁にアクセスする要素は特定の場所やその周辺に偏っている。例えば両端キューの場合、ほとんどの演算は両端やその周辺に対する演算である。そのため毎回根から参照を辿るのは効率が悪い。そこで参照を辿る開始点を変更し、必要に応じてポインタを反転させておき頻繁にアクセスする部分に素早くアクセスできるようにする。この構造を指と言う。以下は完全二分木の両端に対して指を導入した例である(2-3フィンガーツリーではない)。

まず参照を辿る開始点を両端にする。親からそのノードへの参照を反転させる。そして親から親の親への参照も再帰的に反転させていく。すると両端に近い部分へは素早くアクセスできるようになる。完全二分木の両端に指を導入したものは最初の部分を除いて、2つの完全二分木を要素として持つリストとしても見られる。各完全二分木のサイズは2倍ずつに増えていく。

2-3フィンガーツリーは分岐数が2または3である木構造の両端に指を追加したものであり、分岐数が2または3である木のペアを要素として持つリストとしても見られる。ただしそれらの木の根のみは1から4つの子を持てるように条件を緩和する。これは追加と削除を交互に実行しても処理時間を償却定数時間に保つためである。なお根の分岐数は1から3まででもよい。その場合、計算量のオーダーは変わらないものの木は深くなる。2-3フィンガーツリーをリストとして見た場合、完全二分木に指を導入したときと同じように各要素の木は指数関数的に大きくなる。

2-3フィンガーツリーは形式的には次のように定義される。ここでは記法はHaskellを用いた。

 -- 2-3フィンガーツリー
 data FingerTree a = Empty -- 空の木
                   | Single a -- 1つだけ要素を持つ木
                   | Deep (Digit a) (FingerTree (Node a)) (Digit a) -- より深い木
 
 -- 左右の木の根。1から4つの要素を持つ。
 data Digit a = One a | Two a a | Three a a a | Four a a a a
 
 -- 左右の木の根以外。2つまたは3つの要素を持つ。
 data Node a = Node2 a a | Node3 a a a

フィンガーツリーは「空の木」「1つだけ要素を持つ木」「深い木」のいずれかである。深い木は列の最初の数要素・最後の数要素・それ以外を保持するフィンガーツリーからなる。Digitは左右の木の根であり、Nodeは分岐数が2または3である平衡木を表す。ただしDigitやNodeは木の深さによって異なる型を持つ。例えばNode Integerは整数を要素としてもつ深さ1の木であり、Node (Node Integer)は整数を要素として持つ深さ2の木である。この型付けは深いフィンガーツリーは左右に持つ木も深くなるという制約を強制し、アルゴリズムを強固で単純にする。左右の木をDigit(数字)と呼んでいるのはフィンガーツリーが数値表現を利用したデータ構造だからである。

## 演算

フィンガーツリーに対する要素の追加等の各種演算を示す。ここでは次のように図を混ぜた式でも表現する。

### 追加

木の右に要素を追加する演算について示す。左に追加する演算も同様である。

追加演算の演算子を▷で示す。
空の木や、1つだけ要素を持つ木に対する追加は簡単である。

 Empty ▷ a = Single a

 (Single a) ▷ b = Deep (One a) Empty (One b)

深い木に対する追加に関してもDigitが4未満の場合は簡単である。例えば右のDigitが1の場合は次のようになる。

  (Deep pr m (One b)) ▷ c = Deep pr m (Two b c)

Digitが4の場合はより深い木に繰り上がり処理をする。

  (Deep pr m (Four b c d e)) ▷ f = Deep pr (m ▷ (Node3 b c d)) (Two e f)

より深い木の要素は1段深いNodeである点に注意。

### 削除

木を一番右の要素とその要素を削除した木に分割する演算popRについて示す。左側を分割する演算popLも同様である。

削除演算はほとんど追加演算の逆である。1つだけ要素を持つ木からの削除は単純である。

  popR (Single a) = (Empty, a)

  
深い木に関してもDigitが1以外のときは単純である。例えばの場合は次のようになる。

  popR (Deep pr m (Two b c)) = (Deep pr m (One b), c)

Digitが1の場合、繰り下がり処理をする。

  popR (Deep pr m (One b)) = (borrowR pr m, b)

繰り下がり処理はより深い木が空の場合と空でない場合で場合分けする。空の場合は次のようになる。

  borrowR pr Empty = toTree pr

ここでtoTreeは空の木にprの要素を順に追加する関数である。

より深い木が空でない場合は次のようになる。

  borrowR pr m
    = let
        (m', node) = popR m
      in
        Deep pr m' (toDigit node)

ここでtoDigitはNodeをDigitに変換する関数である。Nodeは2つまたは3つの要素を持つので、それらをTwoまたはThreeに変換する。より深い木の要素はNodeである点に注意。

popRで木を変形する様子を図で示す。ここではpopRとborrowRを合わせて1つの式で書いている。より深い木が空の場合は次のようになる。

より深い木が空でない場合は次のようになる。

追加および削除演算の計算量は式を遅延評価する処理系において償却定数時間である。

以下の図は空の木に右から要素を17個追加し、左から1つずつ削除していく様子である。ただし繰り上がりや繰り下がりの様子がわかりやすいようにDigitは3までに制限してある。

### 連結

2つの木を連結する演算は直接定義されるのではなく、2つの木の間に数個の要素を挟んで連結する演算appendを使って定義される。

どちらかの木が空、もしくは1つだけ要素を持つ場合は単純である。例えば右の木が1つだけ要素を持つ場合は次のようになる。

  append(pr, [a, b, c, d, e], Single f) = pr ▷ a ▷ b ▷ c ▷ d ▷ e ▷ f

両方の木が深い木である場合は、再帰的に要素を追加する。一例を示す。

  append(Deep pr m1 (Four a b c d), [e, f, g, h], Deep (Three i j k) m2 sf)
    = let
        m = append(m1, [Node3 a b c, Node3 d e f, Node3 g h i, Node j k], m2)
      in
        Deep pr m sf

### 分割

木を指定した位置で分割するためには、木の各部分に対してその部分が含む要素の数を計算する必要がある。

 class SizeMeasured a where size :: a -> Integer
 
 instance SizeMeasured FingerTree where
   size Empty = 0
   size (Single a) = size a
   size (Deep pr m sf) = size pr + size m + size sf
 
 instance SizeMeasured Digit where
   size (One a) = size a
   size (Two a b) = size a + size b
   -- その他のDigitは省略
 
 instance SizeMeasured Node where
   size (Node2 a b) = size a + size b
   size (Node3 a b c) = size a + size b + size c
 
 newtype Leaf a = Leaf a -- 葉はLeafでくるんでおく。
 instance SizeMeasured Leaf where
   size (Leaf _) = 1
 
実際には木の各部分に要素数のキャッシュを追加しておき、再計算しないようにする。

i番目の葉での分割演算は、i番目の葉を含む要素より左の要素からなる木・i番目の葉を含む要素・i番目の葉を含む要素より右の要素からなる木に分割する演算splitTreeAtを使って定義される。

木が要素を1つだけもつときは単純である。ここで、iは0以上、木のサイズ未満とする。

  splitTreeAt i (Single a) = (Empty, a, Empty)

深い木の場合はi番目の葉の位置により場合分けする。まずi番目の葉が左の木や右の木に含まれる場合は、それを分割すればよい。

  splitTreeAt i (Deep pr m sf)
    | i  size pr + size m -- i番目の葉は右に含まれる
      = let
          (sf1, a, sf2) = splitDigitAt (i - size pr - size m) sf
        in
          (Deep pr m sf1, a, pr2)
    -- 続く

左右の木の分割は単純にi番目より左の要素と、i番目の要素と、i番目より右の要素に分ければよい。

  splitDigitAt i (One a) = (Empty, a, Empty)
  splitDigitAt i (Two a b) | i