2-3 フィンガーツリー

2-3フィンガーツリーとは

2-3フィンガーツリーは、列（シーケンス）を効率的に扱うための永続データ構造です。主な特徴として、以下の点が挙げられます。

両端への追加・削除が高速: 償却定数時間で実行可能
連結・分割が効率的: 対数時間で実行可能
柔軟な応用: 分割演算を応用することで、優先度付きキューや探索木などのデータ構造を実装可能

このデータ構造は、2006年にRalf HinzeとRoss Patersonによって発表されました。

主な利用

関数型プログラミング言語でよく利用され、以下のような実装例があります。

Haskell: `containers`パッケージの`Data.Sequence`モジュール（列に特化）、`fingertree`パッケージ（汎用的な実装）
Scala: 標準ライブラリには含まれていませんが、`scalaz`などのライブラリで利用可能
その他、様々なプログラミング言語で実装

2-3フィンガーツリーの構造

2-3フィンガーツリーは、2または3個の子を持つ木構造に「指（finger）」と呼ばれる構造を導入したものです。これにより、頻繁にアクセスする要素への効率的なアクセスを可能にします。

指の概念

通常の平衡木では、要素にアクセスするために根から葉まで参照を辿る必要があり、要素数に対して対数時間の計算量が必要です。しかし、実際にはアクセス頻度の高い要素は特定の場所に偏っていることが多く、例えば両端キューでは両端付近の要素へのアクセスがほとんどです。

そこで、参照を辿る開始点をアクセス頻度の高い場所に近づけ、必要に応じてポインタの向きを反転させることで、高速なアクセスを実現します。この構造を「指」と呼びます。

構造の詳細

1. 指の導入: 木の両端に指を導入し、親ノードへの参照を反転させます。これにより、両端付近の要素へのアクセスが高速になります。
2. 木のリストとしての表現: 指を導入した木は、複数の木を要素として持つリストとして捉えることもできます。各木のサイズは指数関数的に大きくなります。
3. 2-3木との組み合わせ: 2-3フィンガーツリーは、分岐数が2または3である木構造の両端に指を追加したものです。木の根は1〜4個の子を持つことができ、これは追加・削除時の償却定数時間を保証するための条件です。

形式的な定義

Haskellでの定義例を示します。

haskell
data FingerTree a = Empty -- 空の木
| Single a -- 1つの要素を持つ木
| Deep (Digit a) (FingerTree (Node a)) (Digit a) -- より深い木

data Digit a = One a | Two a a | Three a a a | Four a a a a -- 左右の木の根（1〜4個の要素）

data Node a = Node2 a a | Node3 a a a -- 左右の木の根以外（2または3個の要素）


`FingerTree`は、「空の木」、「1つの要素を持つ木」、「深い木」のいずれかです。
`Deep`は、列の最初と最後の数要素を表す`Digit`と、残りの要素を保持するフィンガーツリーで構成されます。
`Digit`は木の根を表し、`Node`は根以外のノードを表します。
`Digit`や`Node`の型は木の深さによって異なり、これにより深いフィンガーツリーは左右に持つ木も深くなるという制約が強制されます。

2-3フィンガーツリーの演算

要素の追加

木構造の右端に要素を追加する演算（`▷`）を例に説明します。左端への追加も同様です。

空の木への追加:


Empty ▷ a = Single a


1つの要素を持つ木への追加:


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


深い木への追加 (Digitが4未満の場合):


(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)

要素の削除

木構造の右端の要素を削除する演算（`popR`）を例に説明します。左端からの削除も同様です。

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`は、より深い木が空かどうかで処理を分け、必要に応じて繰り下がり処理を行います。

追加・削除演算は、遅延評価を行う処理系において償却定数時間で実行できます。

連結

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

分割

木を指定した位置で分割するためには、まず各部分木に含まれる要素数を計算する必要があります。

分割演算は、要素の位置を特定し、その要素より左側の木、要素自身、右側の木に分割する`splitTreeAt`演算を使って定義されます。

分割演算は、データ構造を一般化することで、様々なデータ構造を実装できる強力なツールとなります。要素数を計算する代わりに、ノードの特性に応じた値を計算し、述語を使って分割点を決定することで、柔軟なデータ構造を構築できます。

一般化された分割演算

一般化された分割演算では、各ノードについて、サイズではなく実装するデータ構造に応じた値を計算し、キャッシュできるようにします。この値はモノイドである必要があります。また、分割点を決定するための述語が必要です。

分割演算では、アキュムレータを用意し、再帰呼び出しに入る前に左側の部分木の値を累積していき、述語を満たす要素を探します。

implicit recursive slowdown

2-3フィンガーツリーは、`implicit recursive slowdown`という手法に基づいて構成されています。これは、`recursive slowdown`に遅延評価を導入したもので、計算量を償却計算量に緩めて簡略化したものです。`recursive slowdown`では、親ノードをn回処理する間に、子ノードをnより少ないm回処理します。この性質により、全体の計算量が親ノードの計算量の定数倍に抑えられ、要素の追加や削除演算が償却定数時間で実行できます。

応用

優先度付きキュー

`measure`関数は、部分木が持つ最大の優先度を返します。分割は、優先度が木全体の最大の優先度と等しい要素で行います。

探索木

`measure`関数は、部分木が持つ最後のキーを返します。キーkを挿入する際は、木をkより小さい部分とk以上の部分に分割し、間にkを入れて連結します。これにより、キーが昇順に並ぶ平衡探索木を実装できます。

統計量の計算

`measure`関数は、部分木が持つ要素の数、平均、分散×要素数の組を返します。これにより、データ列の部分列に対する統計量を効率的かつ安定的に計算できます。

まとめ

2-3フィンガーツリーは、効率的な永続データ構造であり、柔軟な応用が可能です。関数型プログラミングにおいて、シーケンス処理や様々なデータ構造の構築に役立ちます。

もう一度検索