トライ木

トライ木は共通接頭辞を共有して文字列を保存し、一辺が一文字に対応します。自動補完やプレフィックスルーティングに使います。長さ L の挿入、完全一致検索、接頭辞検索は平均 O(L) です。終端マークで単語と途中の接頭辞を分けます。

car と cat は c、a の経路を共有し、r と t で分かれます。ノードへ到達すれば接頭辞は存在します。完全な単語の存在には終端マークも必要です。

一辺に一文字

根は文字を保存しません。根の子マップは先頭文字をキーとし、その先も次の文字を子ノードへ対応付けます。各ノードは根からの経路全体の接頭辞を表します。c の下の a は ca であり、木の中のすべての a ではありません。

insert(word) は根から一文字ずつ読みます。対応する子があれば再利用し、なければ作成します。最後の文字のノードに終端マークを付けます。car を入れて c -> a が存在しても、ca が単語になるわけではありません。

二つの検索は同じ文字経路を使います。search(word) は全経路と終端マークを要求します。startsWith(prefix) は接頭辞を読み切ればよく、終端を問いません。startsWith("ca") は到達だけ、search("ca") はマークまで確認します。

操作をステップで追う

既定は空の根から五つの操作を実行します。

1. insert("car")：c、a、r を読む。子がないため三ノードを順に作って進み、r を終端にする。単語一つ、単語の総文字数 3、文字ノード数 3。
2. insert("cat")：c と a を再利用し、t だけ作って終端にする。二単語は計六文字だが、文字ノードは四つ。共通の c と a を一度ずつ保存する。
3. search("car")：c、a、r をたどり、終点にマークがあるため true。
4. startsWith("ca")：c と a の経路があるので true。a の終端マークは要求しない。
5. search("ca")：同じ a に到達するが、終端マークがなく false。同じ経路でも判定条件が違う。

画面は現在の文字と辺を琥珀色で強調し、一致した接頭辞を中程度、無関係の枝を薄く表示します。チェック付きの輪が完全な単語を示します。最後の二操作は、その輪を要求するかどうかが違います。

時間・空間計算量

L は処理する単語または接頭辞の文字数です。

子マップの一回の検索が平均 O(1) と仮定します。保存済み単語を順に比較せず、入力を一度読み、各文字が一辺を選びます。一回の子選択が定数時間でも、最大 L 文字を処理する全操作は O(1) にはなりません。検索は最初に欠けた辺で止まり、挿入と成功した検索は L 文字すべてを読みます。

Many words は八単語を保存してから search("cap") を実行します。それでもたどるのは c、a、p の三辺です。八単語を走査せず、問い合わせの長さで仕事量が決まります。

全空間は O(P) で、P は保存した全単語に含まれる異なる非空接頭辞数です。car と cat は六文字でも P は 4。共有がなければ総文字数と一致します。No sharing の ant、boy、cup は九文字に九文字ノードを使います。

完全一致だけならハッシュ集合の方が単純で、メモリも少なく済むことがあります。自動補完、プレフィックスルーティング、ca 以下のキー列挙などが必要な時にトライ木を選びます。各ノードの子マップと、キャッシュに不利なアクセスが代価です。

プレイヤーは文字ノード 24 個、単語長 6 まで表示します。ラベルを読める大きさに保つためで、構造の制限ではありません。実装はメモリやアプリケーションの方針まで成長できます。

境界ケース

• 空の木：非空文字列への両検索は、最初の文字の子がなく失敗する。
• 一文字の単語：根が直接そのノードを指し、終端マークが完全一致を決める。
• 重複挿入：全ノードを再利用し、既存のマークを再設定する。ノード数、単語数、保存単語の総文字数は変わらない。
• 単語が接頭辞でもある：car と care を入れると、r は終端であり、子 e も持つ。
• 共有が少ない：検索は O(L) のままだが、ほぼ一文字一ノードとなり、空間の節約がなくなる。

よくある間違い

• 到達できる経路をすべて単語とする。 car の挿入後も search("ca") は false。終端を調べます。
• startsWith で終端を要求する。 接頭辞は経路だけで十分です。終端も要求すると完全一致検索になります。
• ない子へ先に進む。 挿入は children[ch] を作ってから node を移します。
• 根を文字ノードに数える。 根は入口で文字を持ちません。共有の比較では根以外を数えます。
• 全操作を O(1) とする。 平均 O(1) の選択を最大 L 回行うので O(L) です。