问题 哪个节点数据结构用于trie

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

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

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

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

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

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

希望这可以帮助！

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

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

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

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

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

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

希望这可以帮助！