2-3 フィンガーツリー

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

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

Haskellでは列に特化した実装がData.Sequenceとしてベースライブラリに含まれる。列に限定しない汎用の実装もfingertreeパッケージとして用意されている。

• 出典: フリー百科事典『ウィキペディア（Wikipedia）』
• [ 2-3 フィンガーツリーの改定履歴 ]