時間inorder後継メソッドを使用したBSTの印刷の複雑さ

Question

私は、バイナリ検索ツリー（BST）内で次のinorder successorを見つける方法を持っています。 「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の最小ノードが指定されています。 BSTのすべてのノードを印刷するために「inorderSuccessor」を継続的に呼び出すメソッドを記述すると、合計時間の複雑さはどのくらいですか？私はそれがO（n * h）だと思います。あれは正しいですか？

Answer 1

O（nh）でインオーダーの後続を見つけることで、すべてを印刷するコストを上限にすることはできますが、それは実際には厳しい境界ではありません。ツリーの高さとは関係なく、ランタイムが実際にΘ（n）であることを示すことができます！

これを見る1つの方法は、ツリーの各エッジが何回訪問されたかを調べることです。すべてのインオーダートラバーサルの実行をトレースすると、各エッジを1回だけ正確に1回ずつ移動し、各エッジを正確に1回上に移動し、実行される全作業が各エッジが訪問された回数に比例することがわかります。 nノードツリーのエッジの数はΘ（n）です。したがって、実行時には境界になります。

は、それぞれの操作に時間がかかることに注意してください（1）。それは真実ではない。あなたが言うことができるのは、が合計でであり、それぞれが,のO（1）時間かかることです。