trie以当前节点或节点结束

Question

鉴于trie的节点如此：

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

在单词的末尾（案例1）

，endofword bool会更好

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

或创建一个空的char节点并在那里有endofword（案例2）

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

从我看到的所有教程中，他们建议后一种选择，但这不会使事情更加混乱吗？对于包含招手和招手的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缓存中加载时，但是可以通过使用单个终止器节点来缓解这一点。也就是说，除非有人需要从孩子身上撤回父母 - 如果我能想象为什么有人需要它）。

Answer 2

创建其他对象来表示grapf叶有什么意义？在任何算法实现中，您都必须检查endOfWord是否设置为true或false。介绍其他对象不会使实现更容易，它将导致内存浪费。

Answer 3

一个原因可能是，如果您使用特殊字符（例如代码点0），则根本不需要单词结束标志。