哪个节点的数据结构要用于一个trie

Question

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

Answer 1

这些选项各有其优点和缺点。

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

如果将子节点存储在链接列表中，则查找子节点所需的时间为O（| Σ |），因为您可能需要扫描链表的所有节点以查找你想要的孩子。另一方面，空间效率会非常好，因为您只储存您正在使用的孩子。您也可以考虑在这里使用固定大小的阵列，它具有更好的空间使用率，但会导致非常昂贵的插入和删除操作。

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

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

简而言之，数组查找速度最快，但在最糟糕的情况下其空间使用率最差。一个静态大小的数组具有最好的内存使用情况，但是昂贵的插入和删除。哈希表具有快速查找和良好的内存使用情况（平均而言）。二叉搜索树位于中间的某处。我会建议在这里使用哈希表，但如果你对空间进行溢价并且不关心查找时间，那么链表可能会更好。另外，如果你的字母表很小（比如你正在制作一个二进制的trie），那么数组的开销不会太坏，你可能想要使用它。

希望这会有所帮助！

Answer 2

如果你正在尝试构建字符串的trie，我会建议使用数组，然后使用particia树（空间优化trie）。 http://en.wikipedia.org/wiki/Radix_tree

这将允许您快速查找数组，并且不会浪费太多的空间，如果某些节点的分支因子很低。