时间使用中继方法打印BST的复杂性

我有一种方法来查找二进制搜索树（BST）中的下一个中序继任者。 “inorderSuccessor”方法将BST的任何节点作为输入并输出下一个中间继承者。方法和树类的定义如下：时间使用中继方法打印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）。那是对的吗？

来源

2017-06-13 DIRECTIONNZ

打印BST中的所有节点？那不是'O（* BST *中的节点数量）'吗？无论他们是按顺序，先后顺序还是其他顺序枚举？ –

@AlexBollbach有一些打印方式不能在线性时间内运行，比如做一个DFS打印深度为0的所有节点，然后是深度为1的所有节点等等，所以它不是全部不合理的问题。 – templatetypedef

虽然这个问题指定了序列的使用。 –

您可以通过总是在O（nh）处找到inorder后继来限制打印所有内容的成本，但这实际上并不是一个严格的限制。您可以显示运行时实际上是Θ（n），与树的高度无关！

看到此的一种方法是查看树中每个边缘被访问了多少次。如果你追踪所有这些遍历的执行情况，你会发现你精确地沿每条边走一次，每条边只上一次，并且完成的工作量与每条边访问的次数成正比。 n节点树中的边数为Θ（n），因此是运行时限。

请注意，您不能说，每个单独的操作将需要时间O（1）。这不是真的。你可以说的是，合计每个人需要O（1）时间的平均。

来源

2017-06-14 00:10:50 templatetypedef

谢谢你的解释。这非常有帮助！ – DIRECTIONNZ

时间使用中继方法打印BST的复杂性

回答

相关问题