为什么在平衡树的情况下，这个BST验证算法是O(n) ?

Question

我试图写一个算法，给定一个完整的告诉我它是不是一个二叉搜索树(BST)我需要提供一个时间复杂度为O(n)的算法，其中n为树中的节点数。

我想出了这个解决方案(伪代码):

def isBST(x):
if x=NIL: return True
if min(x.right) < x.value or max(x.left) > x.value: return False
isBST(x.left)
isBST(x.right)
return True

其中min(X.right)是由x定义的右子树中的最小值:

def min(x):
while x.left:
x = x.left
return x.value

max(X.left)取左子树最大值

我在网上看到这种解在平衡/满树的情况下的运行时间为O(N)，因为递归方程将是:

T(n) = T(n/2) + O(logn)

这是否表示O(n)时间复杂度?如果是，为什么?如果不是，我怎么让它变成O(n)?

Answer 1

首先，我应该提到你的函数中有一个bug:它对递归调用返回的布尔值不做任何处理，因此即使其中一个返回false，执行继续并返回true。

正确的代码应该这样处理递归调用:

return isBST(x.left) and isBST(x.right)

---

在最坏情况下，即给定树确实是BST时，时间复杂度为0(𝑛)。

当给定的树不是BST并且if条件的第一次执行为真并且执行结束时，最佳情况是0 (log𝑛)。一个min(𝑛)的调用负责那个O(log𝑛)。

当给定的树是BST时，所有节点轮流成为函数的参数，并且以NIL作为参数也称为O(𝑛)次，每个叶节点(左和右)两次。

分析中比较困难的部分涉及min(𝑛)和max(𝑛)的调用。这些访问节点，其中是给定节点的高度。乍一看，这似乎会使时间复杂度比0(𝑛)更差，但是对于叶子，的值是0，并且对于一半的节点都是如此，而另一个极端(根)的等于树的高度，但是只有一个根。

这类似于如何以0(𝑛)时间复杂度构建堆，使用Floyd的堆构建算法-就像这里一样-涉及每个节点的log -步骤。结果仍然使整个操作为0(𝑛)。我指的是如何构建一个堆是O(n)的时间复杂度?找到很多解释为什么它仍然是0的答案(𝑛)。这个算法的推理是一样的。

Answer 2

您的时间复杂度方程应为T(n) = 2T(n/2) + O(log(n))。因为在你的函数中，你有一些恒定的检查条件(if)除了在每个子树中找到最小和最大(最坏的情况下是log(n))以及在根的左右子节点上进行两次递归调用。现在，T(n)的复杂度是多少?你说得对!T(n)在O(n)中。你可以用主定理来证明。

同样，如果查找最小和最大只是搜索子树的所有成员，时间复杂度将变为O(nlog(n))，因为循环将变为T(n) = 2T(n/2) + O(n)