Trie数据结构的优势介绍 _数据结构

Tries是存储字符串的树。节点的最大子节点数等于字母表的大小。Trie支持O(L)时间内的搜索、插入和删除操作，其中L是键的长度。
哈希:在哈希中，我们将键转换为一个小值，该值用于索引数据。哈希支持平均O(L)时间内的搜索、插入和删除操作。
自平衡BST：自平衡二叉搜索树(BST)(如红黑树、AVL树、展开树等)中搜索、插入和删除操作的时间复杂度为O(L * Log n)，其中n为单词总数，L为单词长度。自平衡bst的优势在于，它们保持了操作的顺序，使最小、最大、最近(下限或上限)和第k大等操作更快。详情请参考BST比哈希表的优点。
为什么选择Trie？：-

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

Trie问题：-
trie的主要缺点是它们需要大量的内存来存储字符串。对于每个节点，我们有太多的节点指针(等于字母表中的字符数)，如果考虑到空间，那么三元搜索树可以首选用于字典实现。在三元搜索树中，搜索操作的时间复杂度为O(h)，其中h为树的高度。
三元搜索树还支持Trie支持的其他操作，如前缀搜索、字母顺序打印和最近邻居搜索。
【Trie数据结构的优势介绍】关于trie数据结构的最终结论是，它们更快，但需要巨大的内存来存储字符串。