基本プレフィックスツリーの実装に関する質問

Question

私は基本的なプレフィックスツリーまたは "trie"を実装しました。トライは、このようなノードで構成されています

// pseudo-code 
struct node { 
    char c; 
    collection<node> childnodes; 
}; 

は、私は私のトライに次の単語を追加言う：「アップル」、「箱舟」と「猫」。今、私が "Ap"や "Ca"のような接頭辞を検索すると、私のtrieの "bool containsPrefix（string prefix）"メソッドが正しくtrueを返します。

"Cat"と "Ark"ではtrueを返しますが、上記の例では "App"ではfalseを返すメソッド "bool containsWholeWord（string word）"を実装しています。

トライのノードで「endOfWord」フラグを使用するのは一般的ですか？これは、ルックアップされている文字列が実際にプレフィックスだけでなくトライに入力された単語であるかどうかを判断するのに役立ちます。

乾杯！

Answer 1

「App」と「Apple」の両方を保存する必要があり、「Appl」は保存しない場合は、endOfWordフラグが必要です。

また、同じ文字を持つ2つのノードを（時々）使用してデザインに合わせることもできます。したがって、 "Ap"は子ノードに属していなければなりません。リーフノード "p"と内部ノード "p"に子 "l"があります。

Answer 2

通常、キーの終わりはリーフノードで示されます。

• 子ノードは空です。または
• あなたは、キーのプレフィックスといくつかの子ノードを持つ枝を持っています。

デザインにリーフ/空のノードがありません。例：ヌル