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

Question

由于我无法找到这个问题的答案：

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

标签： algorithmdata-structuresbinary-search-tree

Answer 1

我不确定我是否正确理解了这个问题，以及您是否被问及摊销复杂性或特定的最佳情况。

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

想象一棵不平衡树，其根的值为X，具有较大的左子树（值小于X），但右子树为空（没有大于 的值X）。

现在，如果您尝试找到任何大于X（好的情况）的值，您将意识到仅通过访问根就没有这样的值。