java - 使用顺序后继方法打印 BST 的时间复杂度

Question

我有一种方法可以在二叉搜索树 (BST) 中查找下一个顺序后继者。 “inorderSuccessor”方法将 BST 的任意节点作为输入并输出下一个中序后继节点。方法和树类定义如下:

class BSTInorderSuccessor{
  public static Node inorderSuccessor(Node node) {
    if (node.right != null) {
      return minValue(node.right);
    }
    Node parent = node.parent;
    while (parent != null && node == parent.right){
      node = parent;
      parent = parent.parent;
    }
    return parent;
  }
}

class TreeNode{
  int data;
  Node left;
  Node right;
  Node parent;
  public TreeNode(int data){
    this.data = data;
    this.left = null;
    this.right = null;
    this.parent = null;
  }
}

假设BST的高度是h，这个树结构中有n个节点。我知道“inorderSuccessor”方法的时间复杂度是 O(h)。

我的问题是:给定 BST 的最小节点。当我写一个方法不断调用“inorderSuccessor”来打印BST的所有节点时，总时间复杂度是多少？我认为是 O(n * h)。对吗？

Answer 1

您可以通过始终在 O(nh) 处找到中序后继来限制打印所有内容的成本，但这实际上并不是一个严格的界限。您可以证明运行时间实际上是 Θ(n)，与树的高度无关!

查看这一点的一种方法是查看树中每条边被访问的次数。如果跟踪所有这些中序遍历的执行情况，您会发现每条边向下恰好一次，每条边向上恰好一次，完成的总工作量与每条边被访问的次数成正比。 n 节点树中的边数为 Θ(n)，因此受运行时间限制。

请注意，您不能说每个单独的操作都需要时间 O(1)。这不是真的。您可以说的是，总的来说每个人都花费了 O(1) 时间的平均。