algorithm - 寻找二叉树最小值的时间复杂度

Question

我写了一个递归函数来查找二叉树的最小值(假设它是无序的)。

代码如下。

//assume node values are positive int.
int minValue (Node n) {
if(n == null) return 0;
leftmin = minValue(n.left);
rightmin = minValue(n.right);
return min(n.data, leftmin, rightmin);
}

int min (int a, int b, int c) {
int min = 0;
if(b != 0 && c != 0) {
if(a<=b) min =a;
else min =b;
if(min<=c) return min;
else return c;
}
if(b==0) {
if(a<=c) return a;
else return c;
}
if(c==0) {
if(a<=b) return a;
else return b;
}
}

凭直觉，我猜 minValue 函数的时间复杂度是 O(n)。

这是正确的吗？谁能给出 minValue 函数时间复杂度的正式证明？

Answer 1

假设您的二叉树是无序的，那么您的搜索算法将有 <em>O(N)</em>运行时间，所以你的直觉是正确的。需要的原因<em>O(N)</em>平均而言，您必须搜索树中一半的节点才能找到输入。但这假设树是完全无序的。

对于排序的和平衡二叉树，搜索将花费<em>O(logN)</em> .这样做的原因是搜索将只需要沿着树向下遍历一条路径。具有 N 个节点的平衡树的高度为 log(N)，这解释了搜索的复杂性。例如考虑以下树:

      5
    /   \
  3      7
 / \    / \
1   4  6   8

树中有 8 个(实际上是 7 个)节点，但高度仅为 log(8) = 2。您可以说服自己，您只需要遍历这棵树一次即可找到一个值或失败。

请注意，对于不平衡的二叉树，这些复杂性可能不适用。