Temps Complexité de l'impression BST en utilisant la méthode successeur inorder

Question

J'ai une méthode pour trouver le successeur inorder suivant dans un arbre de recherche binaire (BST). La méthode "inorderSuccessor" prend n'importe quel noeud du BST en entrée et sort le successeur suivant. Le procédé et la classe de l'arbre sont définis comme suit:

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; 
    } 
} 

Supposons que la hauteur de la BST est H, et il y a N noeuds au sein de cette structure arborescente. Je sais que la complexité temporelle de la méthode "inorderSuccessor" est O (h).

Ma question est: Étant donné le plus petit nœud de la BST. Quand j'écris une méthode pour appeler continuellement "inorderSuccessor" pour imprimer tous les nœuds de la BST, quelle est la complexité totale du temps? Je pense que c'est O (n * h). Est-ce exact?

Answer 1

Vous pouvez limiter le coût d'impression de tout en trouvant toujours le successeur inorder à O (nh), mais ce n'est pas vraiment une limite serrée. Vous pouvez montrer que le runtime est effectivement Θ (n), indépendamment de la hauteur de l'arbre! Une façon de voir ceci est de regarder combien de fois chaque arête de l'arbre est visitée. Si vous tracez l'exécution de toutes ces traversées, vous constaterez que vous descendez chaque bord exactement une fois et que vous montez chaque bord exactement une fois, et le travail total est proportionnel au nombre de fois que chaque bord est visité. Le nombre d'arêtes dans un arbre à n nœuds est Θ (n), d'où la limite d'exécution.

Notez que ne peut pas dire que chaque opération prendra du temps O (1). Ce n'est pas vrai. Ce que vous pouvez dire est que dans l'ensemble chacun prend une moyenne de O (1) temps.