Trie数据结构的优势介绍

2021年4月2日11:53:56 发表评论 674 次浏览

Tries是存储字符串的树。节点的最大子节点数等于字母表的大小。Trie支持O(L)时间内的搜索、插入和删除操作,其中L是键的长度。

哈希:在哈希中,我们将键转换为一个小值,该值用于索引数据。哈希支持平均O(L)时间内的搜索、插入和删除操作。

自平衡BST:自平衡二叉搜索树(BST)(如红黑树、AVL树、展开树等)中搜索、插入和删除操作的时间复杂度为O(L * Log n),其中n为单词总数,L为单词长度。自平衡bst的优势在于,它们保持了操作的顺序,使最小、最大、最近(下限或上限)和第k大等操作更快。详情请参考BST比哈希表的优点。

为什么选择Trie? :-

  1. 使用Trie, 我们可以在其中插入和查找字符串O(长)时间在哪里大号表示单个单词的长度。这显然比BST快。由于它的实现方式, 这也比散列更快。我们不需要计算任何哈希函数。不需要碰撞处理(就像我们在开放式寻址和单独链接)
  2. Trie的另一个优势是, 我们可以轻松按字母顺序打印所有单词使用散列不容易实现。
  3. 我们可以有效地做使用Trie进行前缀搜索(或自动完成).

Trie问题:-

trie的主要缺点是它们需要大量的内存来存储字符串。对于每个节点,我们有太多的节点指针(等于字母表中的字符数),如果考虑到空间,那么三元搜索树可以首选用于字典实现。在三元搜索树中,搜索操作的时间复杂度为O(h),其中h为树的高度。

三元搜索树还支持Trie支持的其他操作,如前缀搜索、字母顺序打印和最近邻居搜索。

关于trie数据结构的最终结论是,它们更快,但需要巨大的内存来存储字符串。


木子山

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: