我有一种方法可以在二进制搜索树（BST）中查找下一个inorder后继 . “inorderSuccessor”方法将BST的任何节点作为输入并输出下一个inorder后继 . 方法和树类定义如下：
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） . 那是对的吗？
1 回答
您可以通过始终在O（nh）找到inorder后继来限制打印所有内容的成本，但这实际上并不是一个严格的限制 . 您可以显示运行时实际上是Θ（n），与树的高度无关！
一种看待这种情况的方法是查看树中每个边缘被访问的次数 . 如果你追踪所有那些inorder遍历的执行情况，你会发现你只是每个边缘向下走一次并且每个边缘只上升一次，并且完成的总工作量与每个边缘被访问的次数成比例 . n节点树中的边数是Θ（n），因此运行时绑定 .
请注意，您不能说每个操作都需要花费时间O（1） . 这不是真的 . 你可以说的是，总的来说每个人平均花费O（1）的时间 .