algorithm - 哪个节点数据结构用于 trie

Question

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

Answer 1

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

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

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

如果您将子节点存储在哈希表中，那么找到一个子节点的(预期)时间将为 O(1)，并且内存使用量将仅(大致)与您拥有的子节点数量成正比。有趣的是，因为您事先知道要散列的值是什么，所以您可以考虑使用 dynamic perfect hash table以牺牲一些预计算为代价确保最坏情况下的 O(1) 查找。

另一种选择是将子节点存储在二叉搜索树中。这导致了 ternary search tree数据结构。这种选择介于链接列表和哈希表选项之间——空间使用率低，您可以高效地执行前导和后继查询，但由于 BST 中的搜索成本，执行查找的成本略有增加。如果你有一个永远不会发生插入的静态 trie，你可以考虑使用 weight-balanced trees作为每个点的 BST；这为搜索提供了出色的运行时间(O(n + log k)，其中 n 是要搜索的字符串的长度，k 是 trie 中的单词总数)。

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

希望这对您有所帮助!