Double Array Trie
第 2 版(2008-11-11 22:43:17 · akkun_choi)を表示しています。 最新版に戻る
Trieの実装といえばこれ。
普通の配列だとsparseになる。リストだとキー数に比例して遅くなって効率悪い。
Double Array Trieでは、2つの配列を使う。ひとつは文字を整数にマッピングしたものと、もうひとつはリンク関係を記述したもの。Baseの値に文字の整数表現を足した値が次のノードになっている。
履歴
- 第 2 版akkun_choi2008-11-11 22:43:17
- 第 1 版akkun_choi2008-11-11 22:30:39