Trieとは？
Coddyの「トライ木 - データ構造シリーズ #8」コースのレッスン 2/14。
トライ（"try"と発音し、retrievalの略）は、文字列を文字ごとに格納し、検索するために構築されたツリー状のデータ構造です。ツリー内のすべてのエッジには1つの文字がラベル付けされており、ルートからマークされたノードまでのすべてのパスは、格納された1つの単語を綴ります。
この構造により、接頭辞（プレフィックス）に関する問い合わせが非常に高速になります。トライに"car"で始まる単語が含まれているかどうかを確認するには、何万もの単語が格納されていても、ルートからわずか3文字のルックアップを行うだけです。トライは、オートコンプリート、スペルチェック、IPルーティングテーブルなどの機能の背後にあるエンジンです。
トライの各ノードは、2つの状態を保持します：
children：文字から次のTrieNodeへのマップ。isEndOfWord：ルートからこのノードまでのパスが、挿入された完全な単語を綴っている場合にtrueとなるフラグ。
トライにおける5つの主な操作は以下の通りです：
- Insert（挿入）：単語を追加し、途中で不足しているノードを作成します。
- Search（検索）：完全な単語が格納されているかどうかを確認します。
- StartsWith（前方一致検索）：格納されている単語の中に、指定された接頭辞で始まるものがあるか確認します。
- Delete（削除）：単語を削除し、不要なブランチを整理（プルーン）します。
- WordCount（単語数カウント）：格納されている一意の単語の数を数えます。
それでは、Trieクラスを作成しましょう！
自分で試してみよう
このレッスンにはコードチャレンジは含まれていません。