dil*_*raj 12 algorithm trie data-structures
我是第一次使用trie.我想知道哪个是用于trie的最佳数据结构,同时决定哪个是应该遍历的下一个分支.我正在寻找一个数组,一个hashmap和一个链表.
tem*_*def 12
这些选项中的每一个都有其优点和缺点.
如果将子节点存储在数组中,那么只需索引到数组中就可以非常有效地查找要访问的子节点.但是,每个节点的空间使用率将很高:O(|Σ|),其中Σ是您的单词可以形成的字母集,即使这些子节点中的大多数为空.
如果将子节点存储在链表中,则查找子节点所需的时间将为O(|Σ|),因为您可能需要扫描链表的所有节点以找到所需的子节点.另一方面,空间效率会非常好,因为您只存储您正在使用的孩子.你也可以考虑使用一个固定大小的数组在这里,它具有更好的空间使用量,但会导致非常昂贵的插入和删除.
如果将子节点存储在哈希表中,那么查找子节点的(预期)时间将为O(1),并且内存使用量将仅与您拥有的子节点数成比例(大致).有趣的是,因为您事先知道要进行散列的值是什么,所以您可以考虑使用动态完美散列表来确保最坏情况下的O(1)查找,但会牺牲一些预计算.
另一种选择是将子节点存储在二叉搜索树中.这产生了三元搜索树数据结构.此选择介于链接列表和散列表选项之间 - 空间使用率较低,您可以有效地执行前置和后续查询,但由于BST中的搜索成本,执行查找的成本略有增加.如果你有其中插入不会发生静态线索,您可以考虑使用重量平衡树的每一点的BSTS; 这为搜索提供了出色的运行时间(O(n + log k),其中n是要搜索的字符串的长度,k是trie中的单词总数).
简而言之,阵列查找速度最快,但在最坏的情况下,它的空间使用率最差.一个静态大小的数组具有最佳的内存使用率,但昂贵的插入和删除.哈希表具有相当快的查找速度和良好的内存使用率(平均而言).二进制搜索树位于中间的某个位置.我建议在这里使用哈希表,但是如果你对空间进行溢价并且不关心查找次数,那么链表可能会更好.此外,如果你的字母表很小(比如,你正在制作二进制trie),那么阵列开销也不会太差,你可能想要使用它.
希望这可以帮助!