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

Question

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

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

「Apple」、「Ark」、「Cat」という単語をトライに追加するとします。「Ap」や「Ca」などの接頭辞を検索すると、トライの「bool containsPrefix(string prefix)」メソッドが正しく true を返すようになりました。

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

トライのノードがある種の「endOfWord」フラグを持つのは一般的ですか? これは、検索されている文字列が実際にトライに入力された単語全体であり、単なるプレフィックスではないかどうかを判断するのに役立ちます。

乾杯！

score 2 · Accepted Answer

キーの終わりは、通常、リーフノードを介して示されます。また：

デザインにリーフ/空のノードがありません。null などで示してみてください。

score 1 · Accepted Answer

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

または、(場合によっては) 同じキャラクターを持つ 2 つのノードを使用して、デザインに適合させることもできます。したがって、「Ap」は子ノードにする必要があります。葉ノード「p」と、子「l」を持つ内部ノード「p」です。

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