基本前缀树实现问题

Question

我已经实现了一个基本的前缀树或“trie”。特里树由这样的节点组成：

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

假设我将以下单词添加到我的字典树中：“Apple”、“Ark”和“Cat”。现在，当我查找“Ap”和“Ca”等前缀时，我的 trie 的“bool containsPrefix(string prefix)”方法将正确返回 true。

现在我正在实现“bool containsWholeWord(string word)”方法，该方法将为“Cat”和“Ark”返回 true，但为“App”返回 false（在上面的示例中）。

trie 中的节点通常具有某种“endOfWord”标志吗？ 这将有助于确定正在查找的字符串是否实际上是输入到 trie 中的整个单词，而不仅仅是前缀。

干杯！

Answer 1

键的结束通常通过叶节点来指示。要么：

• 子节点为空；或
• 您有一个分支，带有一个键前缀和一些子节点。

您的设计没有叶/空节点。尝试用例如来表示它一个空值。

Answer 2

如果您需要存储“App”和“Apple”，但不需要存储“Appl”，那么是的，您需要类似

endOfWord

标志之类的东西。

或者，您可以通过（有时）拥有两个具有相同字符的节点来将其融入您的设计中。因此“Ap”必须有子节点：叶节点“p”和带有子节点“l”的内部节点“p”。

Answer 3

它必须是这样的：

class CharTrie final
{
public:

    // (Code)

private:

    // Trie__

    // Structure representing a node in the trie.
    struct Node final
    {
        std::unordered_map<char, std::unique_ptr<Node>> child_node{}; // Map of child nodes.
        bool end_of_string{ false }; // Flag to indicate end of a string
    };

    Node root_{}; // Root node of the trie (Represents a null prefix.)

    // __Trie

    // (Code)
}

演示。

它提供对

root_.child_node[ch]

的访问，时间复杂度为 O(1)。

end_of_string

是必需的，例如，在插入“1234”和“123456”的情况下：公共前缀是：“1234”

（根）
|
1
|
2
|
3
|
4（字符串结尾）
|
5
|
6（字符串结尾）