algorithm - trie 使用哪种节点数据结构

Question

我第一次使用 trie。我想知道在决定应该遍历的下一个分支时，哪个是用于 trie 的最佳数据结构。我正在寻找一个数组、一个哈希图和一个链表。

Answer 1

这些选项中的每一个都有其优点和缺点。

如果您将子节点存储在数组中，那么您可以通过索引数组来非常有效地查找要访问的子节点。但是，每个节点的空间使用率会很高：O(|Σ|)，其中 Σ 是可以组成单词的一组字母，即使这些子节点中的大多数为空。

如果将子节点存储在链表中，则查找子节点所需的时间将是 O(|Σ|)，因为您可能需要扫描链表的所有节点才能找到所需的子节点。另一方面，空间效率会很好，因为你只存储你正在使用的孩子。您还可以考虑在此处使用固定大小的数组，它具有更好的空间使用率，但会导致非常昂贵的插入和删除。

如果您将子节点存储在哈希表中，则（预期）找到子节点的时间将为 O(1)，并且内存使用量仅（大致）与您拥有的子节点数量成正比。有趣的是，因为您事先知道要散列的值是什么，您可以考虑使用动态完美散列表来确保最坏情况的 O(1) 查找，但会牺牲一些预计算。

另一种选择是将子节点存储在二叉搜索树中。这产生了三元搜索树数据结构。这种选择介于链表和哈希表选项之间——空间使用率很低，您可以高效地执行前驱和后继查询，但由于 BST 中的搜索成本，执行查找的成本略有增加。如果您有一个从不发生插入的静态 trie，您可以考虑使用权重平衡树作为每个点的 BST；这为搜索提供了极好的运行时间（O（n + log k），其中 n 是要搜索的字符串的长度，k 是 trie 中的单词总数）。

简而言之，数组查找是最快的，但它在最坏情况下的空间使用是最差的。静态大小的数组具有最佳的内存使用率，但插入和删除的成本很高。哈希表具有相当快的查找速度和良好的内存使用率（平均而言）。二叉搜索树位于中间的某个位置。我建议在这里使用哈希表，但如果您重视空间并且不关心查找时间，则链接列表可能会更好。此外，如果您的字母表很小（例如，您正在制作二进制 trie），则数组开销不会太差，您可能想要使用它。

希望这可以帮助！

Answer 2

如果您尝试仅为字母构建 trie，我建议使用数组，然后使用 particia 树（空间优化的 trie）。 http://en.wikipedia.org/wiki/Radix_tree

这将允许您使用数组进行快速查找，并且如果某个节点的分支因子较低，则不会浪费太多空间。