トライ (データ構造)
(トライ木 から転送)
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2023/01/06 14:51 UTC 版)
トライ木（英: trie）やプレフィックス木（英: prefix tree）とは、順序付き木の一種。あるノードの配下の全ノードは、自身に対応する文字列に共通するプレフィックス（接頭部）があり、ルート（根）には空の文字列が対応している。値は一般に全ノードに対応して存在するわけではなく、末端ノードや一部の中間ノードだけがキーに対応した値を格納している。2分探索木と異なり、各ノードに個々のキーが格納されるのではなく、木構造上のノードの位置とキーが対応している。
- ^ Jun-ichi Aoe (1989). “An Efficient Digital Search Algorithm by Using a Double-Array Structure”. IEEE Transactions on Software Engineering 15 (9): 1066-1077.
- ^ Stephen C. Johnson (1975). “YACC-Yet another compiler-compiler”. Computing Science Technical Report 32: 1-34.
- ^ A.V. エイホ; R. セシィ; J.D. ウルマン; M.S. ラム (2009). コンパイラ―原理・技法・ツール (Information & Computing). ISBN 978-4781912295
- ^ An Implementation of Double-Array Trie
- ^ 13.1 BinaryTrie: A digital search tree
- ^ Bose, Prosenjit; Douïeb, Karim; Dujmović, Vida; Howat, John; Morin, Pat (2010), Fast Local Searches and Updates in Bounded Universes, Proceedings of the 22nd Canadian Conference on Computational Geometry (CCCG2010), pp. 261–264
- ^ a b Willard, Dan E. (1983). “Log-logarithmic worst-case range queries are possible in space Θ(N)”. Information Processing Letters (Elsevier) 17 (2): 81–84. doi:10.1016/0020-0190(83)90075-3. ISSN 0020-0190.
- ^ 13.3 YFastTrie: A Doubly-Logarithmic Time SSet
[続きの解説]
「トライ (データ構造)」の続きの解説一覧
- 1 トライ (データ構造)とは
- 2 トライ (データ構造)の概要
- 3 応用
- 4 実装の工夫
- 5 整数を格納するトライ木
- 6 関連項目
- トライ木のページへのリンク
