c++ - Trie 结束于当前节点或之后的节点

Question

鉴于 trie 具有这样的节点:

struct TrieNode {
    map<char, TrieNode> children; 
    bool endOfWord = false;

    TrieNode() {}
};

endOfWord bool 在单词末尾为真会更好吗(案例 1)

c-a-[t] <--- endOfWord = true;

或者创建一个空的 char 节点并在那里设置 endOfWord(情况 2)

c-a-t-[ ] <--- endOfWord = true;

从我看到的所有教程来看，他们都推荐后一种选择，但这不会让事情变得更加困惑吗？对于包含 beckoned 和 beckon 的 trie，情况 1 看起来像

b-e-c-k-o-[n]-e-[d]

但是情况 2 会有

b-e-c-k-o-n-[e]-d-[ ]

或者这仅仅是我的 trie 是如何实现的问题？

Answer 1

我会选择字母上标记的第一个词尾而不是后继词。

主要原因:搜索时，不需要寻找空的 EoW 后继节点 - 节省 CPU 时间(特别是如果空节点需要加载到 CPU 缓存中，但这可以通过使用单个终止节点来缓解。也就是说，除非有人需要从 child 那里反向引用 parent - 如果我能想象为什么有人需要它，那就打败我吧)。