使用顺序后继方法打印 BST 的时间复杂度
Time Complexity of printing BST using inorder successor method
我有一种在二叉搜索树 (BST) 中查找下一个顺序后继者的方法。 "inorderSuccessor"方法将BST的任意一个节点作为输入,输出下一个中序后继节点。方法和树class定义如下:
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)。对吗?
您可以通过始终在 O(nh) 处找到中序后继来限制打印所有内容的成本,但这实际上并不是一个严格的界限。您可以证明运行时间实际上是 Θ(n),与树的高度无关!
查看这一点的一种方法是查看树中的每条边被访问了多少次。如果跟踪所有这些中序遍历的执行情况,您会发现每条边向下恰好一次,每条边向上恰好一次,完成的总工作量与每条边被访问的次数成正比。 n 节点树中的边数为 Θ(n),因此受运行时间限制。
请注意,您不能说每个单独的操作都需要时间 O(1)。这不是真的。你可以说的是 总计 每个人都需要 平均 的 O(1) 时间。
我有一种在二叉搜索树 (BST) 中查找下一个顺序后继者的方法。 "inorderSuccessor"方法将BST的任意一个节点作为输入,输出下一个中序后继节点。方法和树class定义如下:
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)。对吗?
您可以通过始终在 O(nh) 处找到中序后继来限制打印所有内容的成本,但这实际上并不是一个严格的界限。您可以证明运行时间实际上是 Θ(n),与树的高度无关!
查看这一点的一种方法是查看树中的每条边被访问了多少次。如果跟踪所有这些中序遍历的执行情况,您会发现每条边向下恰好一次,每条边向上恰好一次,完成的总工作量与每条边被访问的次数成正比。 n 节点树中的边数为 Θ(n),因此受运行时间限制。
请注意,您不能说每个单独的操作都需要时间 O(1)。这不是真的。你可以说的是 总计 每个人都需要 平均 的 O(1) 时间。