トライ木（接頭辞ツリー）
単語を追加すると共通接頭辞を共有して枝が伸び、文字を打つと該当パスが点灯します O(長さ) で検索・補完。
英単語A
通常ノード
単語の終端
探索パス点灯
候補（部分木）
登録単語数
—
ノード数（節点）
—
探索結果
—
照合した文字数（手数）
—
「」で始まる候補（部分木に含まれる単語）
トライ木（根 ● から枝が伸びる。各辺が1文字を表す）
トライ木（trie / 接頭辞ツリー）は、文字列を1文字ずつ枝に対応させて木に詰め込むデータ構造です。
根から各ノードへのパスがそのまま接頭辞になり、同じ書き出しの単語は枝を共有します。
だから
単語を追加して枝の共有を観察し、文字列を打って接頭辞の点灯とその先の候補（オートコンプリート）を体感しましょう。
だから
car と card と cat は c→a の部分を共有し、そこから枝分かれします。
検索は文字を1つずつ辿るだけなので、登録数が何万あっても単語の長さ L に比例した手数 O(L) で終わります。単語を追加して枝の共有を観察し、文字列を打って接頭辞の点灯とその先の候補（オートコンプリート）を体感しましょう。
いま何が起きている？
ここがポイント
- パス = 接頭辞 ── 根から下る経路の文字を繋ぐと、その地点までの共通接頭辞になる。
- 枝の共有 ── 同じ書き出しの単語はノードを使い回すので、ノード数は単語数より少なくなる。
- 検索は O(L) ── 文字数 L だけ枝を辿れば判定でき、登録単語数 N に依存しない。
- オートコンプリート ── 接頭辞のノードに着いたら、その下の部分木をたどるだけで候補が全部わかる。