A resource我正在阅读以下内容
If we store keys in binary search tree, a well balanced BST will need time proportional to M * log N, where M is maximum string length and N is number of keys in tree.
我的问题是，上面的时间复杂度M * log N，是在trie中插入一个key，还是在trie中插入N个key，还是在trie中查找？另外，当你说二进制时，我们如何决定左边和右边的内容。是左边a-m，右边n-z，树的第一层等等的字符吗？
最佳答案
时间复杂度 m*logn 是指当您不使用 trie，而是使用平衡 BST 来寻找 n 给定键中的模式时。 p>
原因如下:
您构建 BST 的方式与构建数字数组的方式类似。不过我们不考虑这个预处理步骤。
一旦你构建了一个平衡的 BST，当你搜索给定的模式时，最坏的情况是该模式不存在于 BST 中或存在于叶节点中。这里的关键点是，与带有数字的 BST 不同，您在任何节点的比较复杂度都不是 O(1) 而是 O(m)(因为在最坏的情况下您任何节点处的字符串都与最后一个字母处的模式不同)。
在最坏的情况下，您必须将您的模式与 O(logn) 节点进行比较。
因此最坏情况下的复杂度是O(m*logn)。
关于algorithm - 在二叉搜索树中存储键，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/38671134/