トライ (データ構造)
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2023/01/06 14:51 UTC 版)
整数を格納するトライ木
二分トライ木
二分トライ木（英: binary trie）やビット単位トライ木（英: bitwise trie）とは、整数を格納するトライ木で、上位ビットから 0 また 1 で左右に分岐する[5]。
高速化のためのテクニックとして、下記の２つの方法が使える。
- 葉ノードは子が無く、子を指すポインタが空くので、葉ノード同士を双方向連結リストでつないでしまう。前後のノードを O(1) でたどれるようになる。
- jumpポインタをノードに付け、一気に葉ノードまでジャンプする。
x-高速トライ木
x-高速トライ木（英: x-fast trie）は、検索キーとして与えられた整数以上(以下)の値をもつ、キーに最も近い葉ノードを得る操作(successor, predecessor)を高速にできるようにした二分トライ木のバリエーションである。通常の二分トライ木との相違点は、階層高さごとのハッシュテーブル、葉ノード同士の双方向連結リスト、中間ノードが子ノードを0側(1側)のひとつしか持たない時に格納される、その中間ノード下で最大(最小)値をもつ葉ノードへのリンク(descendant pointer)を持つことである。[6]。階層にたいして二分探索をおこなうことで、木に格納する整数のビット数 w に対し、Successor, Predecessorの時間計算量がO(log w)となる。1982年に Dan E. Willard が発表した[7]。
y-高速トライ木
y-高速トライ木（英: y-fast trie）とは、格納する整数が w ビットの時、x-fast trie に全体の 1/w だけしか格納せず、残りを Treap などの平衡2分探索木に O(w) 個ずつに分けて入れる[8]。これにより全体の空間計算量が、実際に木に格納されたデータの数 n に対し O(n) となり、x-高速トライ木より改善する。また、追加・削除の時間計算量が O(log w) になる。1982年に Dan E. Willard が x-fast trie と同時に発表した[7]。
- ^ 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 関連項目
- トライ (データ構造)のページへのリンク
