トライ木は、共有された文字の接頭辞を1回だけ保存します。各辺は1文字を消費するので、接頭辞の問いには、その接頭辞のノードまで直接たどれば答えられます。ノードに持たせる追加の情報によって、その構造が答えられる問いが決まります:通過数は出現回数を測り、終端フラグは完全な単語を記録します。
それらの状態は異なります。planeを登録するとplanの経路ができますが、planが単語として登録されるわけではありません。このレッスンでは両方の形を構築し、それを使ってルーティングの最短の語根、衝突するラベル、ちょうど1回の置換を許す検索を扱います。コードを書く前に、ノードの各フィールドが何を意味するかを説明してください。その不変条件があれば、空の接頭辞、重複した挿入、単語の終わりをテストしやすくなります。