時間使用中繼方法打印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的複雜性

回答

相關問題