سیف*_*خان 6 c++ hashtable trie treap data-structures
我必须编写一个字典程序作为数据结构和算法本科课程的学期项目,我期望找到最合适的问题解决方案(数据结构).
我考虑过使用哈希表或者trie.有人建议我使用treaps,但还没有能够查看它们.
我的数据库有大约10万个不同的单词及其含义.该程序预期提供的基本功能是插入,更新,删除和搜索单词/定义.如果我设法挤压自动完成和拼写纠正,这将是一个额外的奖励.
所以,我的问题是,牢记我的要求,哪种数据结构最适合我的目的.当我说'最好'时,我要求的数据结构具有最佳的运行时复杂性和低成本(内存要求).
此外,我希望能够有一个算法,它返回以给定前缀开头的所有单词.例如,说我做一个函数调用dictionary.getWordsStartingWith("fic")它应该返回的,与开始的所有单词的列表fic,例如fiction,fictitious,fickle等我知道我能做到这一点,如果我实现了我的字典作为一个线索,我能做到这一点,但是这是可能的用哈希表做到这一点？
如果你想进行自动完成/前缀匹配，你几乎肯定需要一个特里树。哈希表并没有真正使这成为可能；事实上，良好的哈希函数的设计使得即使非常相似的键（例如相同的前缀）也映射到数组的完全不同的部分。出于散列目的，这被视为一项功能。
Treap 基本上是二叉搜索树，它使用随机性 + 堆属性来进行平衡。一般情况下接口是标准的BST树接口；所以它实际上只是一个实现细节，只会导致与红黑树或 AVL 树略有不同的属性。
BST 并不像 trie 那样适合您似乎想要解决的问题。BST 倾向于向下遵循不平等，而 trie 则倾向于向下遵循平等。当您处理数字数据时，不等式比较就是一切，因为相等性非常罕见（因为可能性的空间很大）。对于字符串，每个字符的可能性非常小，因此利用相等性更有意义，从而导致优化，例如在大多数节点上不实际存储键。
总之，我建议继续尝试。它们在这类事情上被大量使用，你可以找到大量的资源来优化它们（特别是空间），因为它们特别用于空间/周期非常宝贵的移动设备上的文本输入。恕我直言，与 BST 相比，它也是一个非常有趣的数据结构，您 a）可能在新生数据结构中大量了解了 BST，并且 b）数据结构真的没有那么有趣吗？除了平衡方案之外的所有内容都是微不足道的，并且平衡方案比其他任何方案都更乏味（RB 树有 7 个真正不同的平衡情况或类似的东西，很难编写 RB 树并使它们全部正确）。
维基百科页面有一些很好的信息： https: //en.wikipedia.org/wiki/Trie。按位尝试看起来特别有趣。