trie木

trie木とは

https://scrapbox.io/files/63a3c85b337cbf001dba45bd.png

Trie木は、データの保存と検索に使用されます。

同じ操作は、別のデータ構造であるハッシュテーブルでも可能ですが、Trieはハッシュテーブルよりも効率的にこれらの操作を行うことができます。

さらに、TrieはHashテーブルに対して独自の優位性を持っています。Trieデータ構造は接頭辞ベースの検索に使用できるのに対し、Hashテーブルは同じようには使用できないのです。

性質

各Trie木には1つのルートノードが存在する。

Trie木の各ノードは文字列を表し、各エッジは1文字を表す。

各ノードはハッシュマップまたはポインタの配列で構成され、各インデックスは文字を表し、文字列が現在のノードで終了しているかどうかを示すフラグを持つ。

トライデータ構造は、アルファベット、数字、特殊文字を含む任意の数の文字を含むことができる。仮にa〜zの文字を含む文字列の場合は、各ノードに必要なポインタは26個だけであり、0番目のインデックスは「a」、25番目のインデックスは「z」文字を表す。

ルートからノードまでの各パスは、単語または文字列を表す。

計算量

探索時間: O(L). Where L is the number of words in the query string.