我第一次使用字典树，想知道在决定应该遍历哪个下一个节点时，最好使用哪种数据结构。我在选择使用数组、哈希表和链表之间犹豫。
2个回答
12
每种选项都有其优点和缺点。如果您将子节点存储在数组中，则可以通过仅索引到数组来非常高效地查找要访问的子节点。然而，每个节点的空间使用率将很高：O（|Σ|），其中Σ是构成单词的字母集合，即使大多数子节点为空。
如果您将子节点存储在链表中，则查找子节点所需的时间将为O（|Σ|），因为您可能需要扫描链接列表的所有节点才能找到所需的子节点。另一方面，空间效率将相当好，因为您只存储正在使用的子节点。您还可以考虑在此处使用固定大小的数组，这样可以获得更好的空间使用率，但会导致非常昂贵的插入和删除。
如果您将子节点存储在哈希表中，则（预期的）查找子节点的时间将为O（1），并且内存使用量仅与您拥有的子节点数量成比例（大约）。有趣的是，因为您事先知道要进行哈希的值，您可以考虑使用动态完美哈希表以确保最坏情况下的O（1）查找，代价是一些预计算。
另一种选择是将子节点存储在二叉搜索树中。这会产生三叉搜索树数据结构。此选择介于链表和哈希表选项之间 - 空间使用率低，可以有效地执行前任和后继查询，但由于BST中的搜索成本，执行查找的成本略有增加。如果您具有静态字典树，其中不进行插入操作，可以考虑在每个点处使用平衡树作为BST；这可以为搜索提供出色的运行时间（O(n + log k)，其中n是要搜索的字符串长度，k是字典树中单词的总数）。
简而言之，数组查找最快，但最坏情况下的空间使用率最差。静态大小的数组具有最佳的内存使用率，但插入和删除昂贵。哈希表具有相当快的查找速度和良好的内存使用率（平均）。二叉搜索树介于两者之间。我建议在这里使用哈希表，但如果您对空间有高要求并且不关心查找时间，则链表可能更好。此外，如果您的字母表很小（例如，您正在制作二进制trie），则数组开销不会太大，您可能需要使用它。
希望这可以帮助！
如果您将子节点存储在链表中，则查找子节点所需的时间将为O（|Σ|），因为您可能需要扫描链接列表的所有节点才能找到所需的子节点。另一方面，空间效率将相当好，因为您只存储正在使用的子节点。您还可以考虑在此处使用固定大小的数组，这样可以获得更好的空间使用率，但会导致非常昂贵的插入和删除。
如果您将子节点存储在哈希表中，则（预期的）查找子节点的时间将为O（1），并且内存使用量仅与您拥有的子节点数量成比例（大约）。有趣的是，因为您事先知道要进行哈希的值，您可以考虑使用动态完美哈希表以确保最坏情况下的O（1）查找，代价是一些预计算。
另一种选择是将子节点存储在二叉搜索树中。这会产生三叉搜索树数据结构。此选择介于链表和哈希表选项之间 - 空间使用率低，可以有效地执行前任和后继查询，但由于BST中的搜索成本，执行查找的成本略有增加。如果您具有静态字典树，其中不进行插入操作，可以考虑在每个点处使用平衡树作为BST；这可以为搜索提供出色的运行时间（O(n + log k)，其中n是要搜索的字符串长度，k是字典树中单词的总数）。
简而言之，数组查找最快，但最坏情况下的空间使用率最差。静态大小的数组具有最佳的内存使用率，但插入和删除昂贵。哈希表具有相当快的查找速度和良好的内存使用率（平均）。二叉搜索树介于两者之间。我建议在这里使用哈希表，但如果您对空间有高要求并且不关心查找时间，则链表可能更好。此外，如果您的字母表很小（例如，您正在制作二进制trie），则数组开销不会太大，您可能需要使用它。
希望这可以帮助！
- templatetypedef
4
对于二叉树，你实际上可以比使用2元素数组做得更好。 - harold
@harold- 很好的观点。在像C或C++这样的语言中，一个包含两个元素的数组和仅持有两个指针之间没有空间差异，但在像Java或Python这样的语言中，你是完全正确的。 - templatetypedef
好的，确实有这种方法，但你也可以通过一些技巧做得更好，让你跳过密钥前导零并直接跳转到对应于那么多前导零的节点。 - harold
@harold- 哦，是的。此外，还有vEB树和y-Fast tries，它们做得更好。 :-) - templatetypedef
0
如果您正在尝试构建仅用于字母的trie，我建议使用数组，然后使用particia树（空间优化trie）。
http://en.wikipedia.org/wiki/Radix_tree
这将允许您使用数组进行快速查找，并且如果某个节点的分支因子较低，则不会浪费太多空间。
- Jack
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接