Spaghetti Source - Trie説明 Trie は文字列のための多分探索木である．各頂点はアルファベットで指定できる枝の集合を持つ．文字列ひとつが根からアルファベットで辺を手繰ることで行き着く頂点に対応する． アルファベットサイズを定数と見たとき，文字列の数に対して trie のサイズは O(m) である．ただし m は蓄えられている文字列の長さの総和．これは通常の二分木で蓄えるのに対して特に不利ではない．検索性能は検索文字列の長さ n に対して O(n) である．これはうまく実装された二分木が O(n + log m) であることと比較して高速である． 結論として，文字列に対して std::map を使いたい場合は trie で代用できないか考えるべきである． 計算量 検索: O(n)，ただし n は検索する文字列長． 使い方 Trie *find(char *t, Trie *v); t に対応する Trie の頂点
