About: 2-3 フィンガーツリー

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