如果平衡树在二叉搜索树中搜索的时间复杂度是多少？

Question

给定的答案是O（nlog（n）），但我也在Wikipedia上查找它，并说它是log（n）。

哪一个是正确的？

另外，搜索不平衡二叉树的最坏情况复杂度是什么？

Answer 1

在平衡的二叉搜索树中，单个搜索的时间复杂度为O(log(n))。也许这个问题要求您n在二叉树中进行搜索，因此总复杂度为O(nlog(n))。

对于不平衡二分搜索树中的单个搜索，最坏情况的复杂度是O(n)。同样，如果您要n在不平衡的树中进行搜索，则总复杂度将为O(n^2)。