为什么这段检查二叉树是否平衡的代码在多次重新计算深度时需要时间 O(n log n)？

Question

此代码旨在检查二叉树是否平衡（平衡被定义为一棵树，使得任何节点的两个子树的高度永远不会相差超过一个。

我理解了运行时间 O(NlogN) 的 N 部分。 N是因为树中的每个节点至少被访问过一次。

int getHeight(TreeNode root){
    if(root==null) return -1; //Base case
    return Math.max(getHeight(root.left), getHeight(root.right))+1; 
}

boolean isBalanced(TreeNode root){
    if(root == null) return true; //Base case

    int heightDiff = getHeight(root.left) - getHeight(root.right);

    if(Math.abs(heightDiff) > 1){
        return false;
    } else{ //Recurse
        return isBalanced(root.left) && isBalanced(root.right);
    }
}

我不明白的是运行时O(NlogN)的logN部分。该代码将跟踪从节点到树底部的每条可能路径。因此，代码应该更像 N2^N 还是什么？怎么一步步得出运行时间为O(NlogN)的结论？

Answer 1

我同意你的看法，运行这段代码的时间不一定是 O(n log n)。但是，我不相信它总是会追踪到从一个节点到树底部的每条路径。例如，考虑这棵树：

这里，计算左右子树的深度，确实会访问每个节点一次。但是，由于发现左右子树之间存在不平衡，因此没有递归地探索左子树就停止递归。换句话说，找到一个递归必须做很多工作的例子需要一些创造力。

你是正确的，高度差的基线检查将花费 Θ(n) 时间，因为必须扫描每个节点。这段代码的问题在于它可能会多次重新扫描节点，因为它会在递归期间重新计算高度差。如果我们希望这个函数运行持续很长时间 - 不一定尽可能长，但持续很长时间 - 我们想要做到

左右子树的高度大致相同，因此递归进行到左子树，但是
树极度不平衡，将大部分节点放在左子树中。

实现此目的的一种方法是创建树，其中右子树只是一个长脊柱，恰好与左子树具有相同的高度，但节点更少。这是具有此属性:

的一种可能的树序列

                              *
                             / \
                *           *   *
               / \         / \   \
      *       *   *       *   *   *
     / \     / \   \     / \   \   \
*   *   *   *   *   *   *   *   *   *

从机制上讲，每棵树都是通过获取前一棵树并在其顶部放置一个向右的脊柱而形成的。在操作上，这些树递归定义如下：

0 序树是单个节点。
一个order-(k+1)树是一个节点，它的左边child是一棵order-k树，右边child是一个高度为k的链表。

请注意，order-k 树中的节点数为 Θ(k²)。您可以通过注意到树具有漂亮的三角形形状来看到这一点，其中每一层都比前一层多一个节点。 1 + 2 + 3 + ... + k 形式的总和计算为 Θ(k²)，虽然我们可以比这更精确，但实际上没有需要这样做。

现在，如果我们在任何一棵树的根上触发递归会发生什么？好吧，递归将从计算左右子树的高度开始，这将报告它们彼此具有相同的高度。然后它将递归地探索左子树以查看它是否平衡。做一些（大量）工作后，它会发现左子树不平衡，此时递归不会分支到右子树。换句话说，在 order-k 树上完成的工作量是 lower-bounded by

W(0) = 1 (有一个节点访问过一次),
W(k+1) = W(k) + Θ(k²).

要查看 W(k+1) 项的来源，请注意我们首先扫描树中的每个节点，并且有 Θ(k²) 个节点扫描，然后递归地将过程应用于左子树。展开这个循环，我们看到在 order-k 树中，完成的总工作是

W(k) = Θ(k²) + W(k-1)

= Θ(k² + (k - 1)²) + W(k - 2)

= Θ(k² + (k - 1)² + (k - 2)²) + W(k - 3)

...

= Θ(k² + (k - 1)² + ... + 2² + 1²)

= Θ(k³).

这最后一步是根据前 k 个立方体的总和得出 Θ(k³) 的事实得出的。

为了结束这件事，我们还有一步。我们已经证明 order-k 树需要 Θ(k³) 总工作量才能使用此递归算法进行处理。然而，我们想要一个运行时间限制，n 是树中的节点总数，而不是 k，树的顺序。使用 k 阶树中的节点数为 Θ(k²) 的事实，我们看到具有 n 个节点的树的阶为 Θ(k^{1 /2})。将其插入，我们看到对于任意大的 n，我们可以使完成的总功等于 Θ((n^1/2)³ ) = Θ(n^3/2)，这超出了您提到的 O(n log n) 建议范围。我不确定这是否是此算法的 worst-case 输入，但它肯定不是一个好输入。

所以是的，你是对的 - 运行时间通常不是 O(n log n)。然而，是情况，如果树是完全平衡的，运行时间确实是O(n log n)。要了解原因，请注意如果树是完美平衡的，则每次递归调用都会

做 O(n) 工作扫描树中的每个节点，然后
对较小的树进行两次递归调用，每棵树的大小大约是前一棵树的一半。

这给出了递归 T(n) = 2T(n / 2) + O(n)，求解为 O(n log n)。但这只是一个特例，不是一般情况。

结论 - 通过稍作修改，此代码在所有情况下都可以在时间 O(n) 内变为运行。不是重新计算每个节点的深度，mae 初始遍历树并用其深度注释每个节点（通过将一些内部字段设置为等于深度或通过辅助 HashMap 将每个节点映射到其深度）。这可以在时间 O(n) 内完成。从那里开始，递归遍历树并检查左子树和右子树的高度是否最多相差一个，需要 O(1) 每个节点在 n 个总节点上工作，总共运行时间为 O(n)。

希望对您有所帮助！

为什么这段检查二叉树是否平衡的代码在多次重新计算深度时需要时间 O(n log n)？

Why does this code to check if a binary tree is balanced take time O(n log n) when it recomputes depths multiple times?

java

big-o

binary-tree

runtime

data-structures