ei1333's page

ホーム > Wiki

トライ木(Trie)

説明

プレフィックス木とも呼ばれる。あるノードの配下の全てのノードには自身に対応する文字列に共通するプレフィックスがあり, ルートには空の文字列が対応している。

使い方

計算量

追加 $O(|m|)$

$m$: 追加する文字列

実装例

Aho-corasick に継承させたいので, そういう実装になってます。

応用: パトリシア木

特に, トライ木で子ノードが $1$ つしかないノードを子ノードとマージして縮約した木をパトリシア木(または基数木) と呼ぶ。無駄な探索を減らすことが出来る。

参考資料