algorithm - Trie 节点是否存储字符值？

Question

我正在学习 Trie，但对维基百科中的描述感到有些困惑： http ://en.wikipedia.org/wiki/Trie

在示例图片中出现字符存储在节点和边缘中？节点类最常见的实现是什么？人们通常将字符存储在节点对象中吗？还是他们通常将其存储在边缘？

谢谢！

Answer 1

字符至少需要存储在边缘（好吧，作为技术，我不确定我是否会将其归类为存储在边缘，而是存储在父级上）。

这背后的原因 - 如果您不知道孩子代表什么字符，您将如何有效地在树中找到一个字符串？在每个级别，您都必须查看所有孩子：

for each child c
  if c.char == character we're looking for

而不仅仅是：（假设children是to ）MapCharacterNode

children.get(character we're looking for)

您当然可以更紧凑地“存储”字符 - 如果您只有小写字符，您可以只拥有一个数组 - Node children[26]，您可以在其中进行如下查找：

children[character we're looking for - 'a']

意思children[0]是 child for 'a'，children[1]child for'b'等。

Answer 2

我认为当你有一个二维数组或矩阵时，边缘更有意义。构建树并将值存储在边中可能很复杂。