二叉树中不成功搜索的最佳情况复杂度

Question

因为我找不到这个问题的答案：

在big-theta表示法中，在不平衡的二进制搜索树中搜索不成功的最佳情况下的复杂度是多少？

Answer 1

我不确定我是否正确理解了这个问题，也不确定是否有人问你摊销的复杂性或具体的最佳情况。

对于特定的情况，最好的情况是O(1)：

想象一个不平衡的树，根保存X的值，左子树很大(值小于X)，但右子树为空(没有大于X的值)。

现在，如果您试图找到任何大于X的值(很好的例子)，您将通过访问根来意识到没有这样的值。

Answer 2

如果左边树的大小是N1，右边树是N2，那么最好的复杂度是Theta(min(log(N1), log(N2)) + 1) (请注意N1 + N2 = N)。