Interactive
トライ木（Trie）可視化
トライ木（Trie／プレフィックス木）は、1文字を1ノードとして木を作り、根から辿った経路がそのまま単語になるデータ構造です。cat・car・card・careのように共通の接頭辞を持つ単語は、その部分を1本の経路として共有します。 単語を挿入すると、既存ノードの再利用と新規ノードの作成が1文字ずつ分かれてステップ再生され、 検索・前方一致では経路を辿った先にある登録済み単語をオートコンプリートとして列挙できます。
単語を挿入
10 / 40 ノード
検索・前方一致
文字ノード（単語の途中）単語の終端（isEnd）このステップで注目
1 / 1
挿入・単語確定
初期状態（cat, car, card, care, dog を登録済み）
ここから単語を挿入したり、検索・前方一致を試したりできます。
ここが分かる
- ノードが表すのは「そこまでの経路＝プレフィックス」であって、単語そのものではない。isEnd（終端）フラグが立ったノードだけが実際に登録された単語——だから "car" を挿入した後でも "care" や "card" を続けて挿入できる。
- 検索は根から1文字ずつ子ノードを辿るだけなので、計算量は木の高さ＝単語の長さに比例する。登録されている単語の総数には依存しない（ハッシュテーブルのように衝突を心配する必要もない）。
- 前方一致（prefix search）は「その経路まで辿って、そこから下のisEndノードを全部集める」だけ——検索エンジンやIDEのオートコンプリート、シェルのタブ補完が高速な理由がこれ。
- IPルーティングテーブルの最長プレフィックスマッチ（LPM）も同じ発想。文字の代わりにビット列（0/1）を経路として使うトライだと考えると、ルータがどのルートを選ぶかも同じ「根から辿れるだけ辿る」操作で説明できる。