存储密钥

Question

一个resource我在阅读状态下

如果我们存储在二叉搜索树键，一个很好的平衡BST需要的时间与M *登录N，其中M为最大字符串长度和N是树中的键的数量。

我的问题是，上面的时间复杂度是M * log N，用于在树中插入一个密钥，还是在树中插入N个密钥，还是在树中搜索？另外，当你说Binary时，我们如何决定左右两边是什么。它是从左边的a-m开始的字符，在树的第一个级别是右边的n-z，以此类推？

Answer 1

文章说，特里树比二叉树为长度为M的字符串，特里需要O（M）的时间和二叉树它需要O（M logN）的时间更好。

Trie有多个孩子而不是两个。

class trienode: 
    char Character 
    map<char, trienode> Children 

class trie: 
    trienode root 

下面是用三个词am，as，at和ok一个线索。 a有3个小孩并且o有1个小孩。

(root) 
    ' ' 
/\ 
    | | 
    a o 
/|\ \ 
| | | | 
m s t k 

Answer 2

的时间复杂度米* LOGN是而是采用了特里时，使用的是平衡BST用于查找ň给出键模式的目的。

原因如下：
您将构建BST，与您对数组数组的操作类似。尽管我们没有考虑这个预处理步骤。
一旦你构建一个平衡BST，当你搜索你的给定模式最糟糕的情况是，该模式中不存在BST或在叶节点存在。这里的关键点是，不像数字的BST在任一节点的比较复杂不O（1）而是O（M）（由于您的字符串在任何节点从你的模式不同，在最坏的情况下最后一封信）。
在你有你的格局与O（LOGN）节点比较最坏的情况。

因此，最坏情况下的复杂性是O（m * logn）。