2-3 フィンガーツリー
(フィンガーツリー から転送)
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/05/15 07:59 UTC 版)
2-3フィンガーツリー(2-3 finger tree、または単にfinger tree)とは、列を表す永続データ構造の一種であり、償却定数時間で両端への追加・削除が可能であり、対数時間で連結・分割・挿入が可能である。また、分割演算を変更すると優先度付きキューや探索木などを実装できる。2006年にRalf HinzeとRoss Patersonが発表した[1][2]。
| ||||||||||||||||||||||||||||||||||
- ^ Ralf Hinze and Ross Paterson, “Finger Trees: A Simple General-purpose Data Structure”, In Journal of Functional Programming Vol. 16, No. 2, 2006, pp. 197–217, doi:10.1017/S0956796805005769
- ^ Finger Trees: A Simple General-purpose Data Structure
- ^ containers: Assorted concrete container types
- ^ Data.Sequence
- ^ fingertree: Generic finger-tree structure, with example instances
- ^ FingerTree - scalaz-core_2.13 javadoc
- ^ Leo J. Guibas, Edward M. McCreight, Michael F. Plass, and Janet R. Roberts, “A new representation for linear lists”, In Proceedings of the ninth annual ACM symposium on Theory of computing (STOC '77), New York, NY, USA: ACM, 1977, pp. 49–60. DOI=10.1145/800105.803395 http://doi.acm.org/10.1145/800105.803395
- ^ sigfpe, “Statistical Fingertrees”, A Neighborhood of Infinity, http://blog.sigfpe.com/2010/11/statistical-fingertrees.html 2011年6月5日アクセス
[続きの解説]
「2-3 フィンガーツリー」の続きの解説一覧
- 1 2-3 フィンガーツリーとは
- 2 2-3 フィンガーツリーの概要
- 3 実行時間
- フィンガーツリーのページへのリンク
