2-3 フィンガーツリー - Wikipedia2-3フィンガーツリー(2-3 finger tree、または単にfinger tree)とは、列を表す永続データ構造の一種であり、償却定数時間で両端への追加・削除が可能であり、対数時間で連結・分割・挿入が可能である。また、分割演算を変更すると優先度付きキューや探索木などを実装できる。2006年にRalf HinzeとRoss Patersonが発表した[1][2]。 関数型プログラミング言語などで使われる。Haskellでは、containersパッケージ[3]に列に特化した実装のData.Sequence[4]が含まれ、列に限定しない汎用の実装もfingertreeパッケージ[5]として存在する。Scalaでは標準ライブラリには含まれていないが、scalaz[6]などのライブラリなどで実装されている。その他、様々なプログラミング言語で実装されている。 構造[編集] 2-3フィンガーツリ
