Bonjour,
C'est quoi ?
Il me semble qu'on peut montrer par récurrence une majoration en . Pour chaque noeud on visite la descendance gauche, le noeud, la descendance droite.

C'est ou simplement ?
Si c'est juste un O, c'est comme GBZM a dit.
Si c'est , c'est parce qu'il faut visiter chaque noeud au moins une fois

C'est bien   mais je veux bien pouvoir le faire aussi quand c'est O(n).

Donc si je comprends bien, on visite chaque nœud au moins une fois, du coup l'appel PARCOURS-INFIXE(x) prend un temps puisque l'arbre binaire contient n nœuds.

Si c'est O(n) alors je suppose qu'on visite chaque nœud une et une seule fois.
La descendance gauche en premier, puis le nœud et enfin la descendance droite.

On peut donc majorer le temps de parcours-infixe d'un noeud par 3 puisqu'un simple nœud a au plus trois éléments (la gauche, le nœud et la droite).

L'arbre contenant n nœuds, et le temps de parcours-infixe de chaque nœud étant , on peut majorer le temps de parcours-infixe de l'arbre de recherche par 3n.

J'espère que je ne raconte pas de bêtises

Pas très clair.

Comment le faire plus rigoureusement ?

Comme je l'ai déjà écrit, tu peux raisonner par récurrence.
Pour chaque noeud A, le parcours fait visite gauche(A), visite A, visite droite (A).
Il convient de traiter à part les cas où gauche(A) ou droite(A) est vide. Dans ce cas je compte que la visite a tout de même un coût 1.
À partir de là tu peux montrer que le coût de "visite gauche(A), visite A, visite droite (A). " est majoré par trois fois le nombre de noeuds du sous-arbre de racine A.

Démonstration par récurrence :

* On considère A un arbre constitué uniquement de gauche(A), A et droite (A).

L'appel PARCOURS-INFIXE (x) ==> le coût de visite gauche (A), visite (A), visite droite (A) est majoré par 3.

* Soit A_n un arbre à n nœuds, supposons que le coût de visite de chaque nœud est majoré par 3n. (1)

Alors pour l'arbre A_{n + 1} constitué de n + 1 nœuds.

On pose N = n + 1.

n étant un entier naturel, N l'est aussi.

Donc pour A_N  composé de N nœuds,  le coût de visite de chaque nœud est majoré par 3N.

Soit pour A_{n + 1}, le coût de visite de chaque nœud est majoré par 3(n + 1).

Conclusion : Si x est la racine d'un sous-arbre à n noeuds, alors l'appel PARCOURS-INFIXE(x) prend un temps O(n).

C'est bon ?

Je ne comprends pas ton raisonnement. mais le comprends-tu toi-même ?
Il convient peut-être de savoir ce qu'on compte quand on évalue la complexité du parcours.
Prenons un exemple. J'emprunte pour cela l'arbre binaire de wikipedia.
Par MasterMatt — Travail personnel, Domaine public, https://commons.wikimedia.org/w/index.php?curid=3398349
On voyage ainsi dans l'arbre :
1-2-4-4-4-2-5-7-7-7-5-8-8-8-5-2-1-3- 3-6-9-9-9-6-6-3-1
et on note en rouge la deuxième occurrence de chaque noeud : c'est le parcours infixe. (Si on note la première occurrence c'est le parcours préfixe, si on note la troisième c'est le parcours postfixe). Ce que je compte, c'est le nombre d'étapes dans le voyage.
Chaque noeud figure trois fois comme étape dans le voyage. On le voit par récurrence sur l'arbre à partir de ce qui se passe pour les feuilles répétées 3 fois (on boucle à gauche s'il n'y a pas de sous-arbre à gauche, on boucle à droite s'il n'y a pas de sous-arbre à droite). Le pas de récurrence utilise ce qui se passe pour le sous-arbre gauche
(ici 2-4-4-4-2-5-7-7-7-5-8-8-8-5-2) et pour le sous-arbre droit (ici 3- 3-6-9-9-9-6-6-3).

Bonjour,

Soit T(n) le temps que met le parcours infixe quant on l'appelle pour la racine d'un sous-arbre à n nœuds. Parcours infixe prend une quantité de temps constante pour un sous-arbre vide (X <> Nil), et donc T(0) = c où c est une constante positive.

Pour n > 0, supposons que parcours-infixe soit appelé sur nœud X dont le sous-arbre gauche à k nœud et dont le sous-arbre droit  a  (n - k - 1) nœuds.  Le temps d'exécution de parcours-infixe(X) est T(n) = T(k) + T(n - k - 1) + d ; d étant une constante positive qui reflète le temps d'exécution de parcours-infixe(X) quand on ne tient pas compte du temps consommé dans les appels récursifs.
On va donc utiliser la méthode de substitution pour montrer que .

Soit la fonction affine :

tel que .

Soit

Pour , on a :



Pour n > 0





avec c' = -c

Conclusion :

T(n) = (c + d)n + c'



Par conséquent si x est la racine d'un sous-arbre à n noeuds, alors l'appel PARCOURS-INFIXE(x) prend un temps O(n).

Tu as recopié le corrigé.

Ah bon ?

Du coup je pense que ce que je viens faire est juste.

Non, mais j'avoue que j'ai eu un coup de pouce de mon prof.

Bonne journée à vous.

5h44, est-ce une heure raisonnable pour poster des maths ?

Bonsoir, si on veut faire comme dans mon message précédent, alors je crois que l'énoncé doit préciser au moins que T(n) = (c + d)n + c.

Du coup je crois que GBZM avait raison de penser que j'ai recopié la correction.

Je pense que faire comme il m'indique est plus correct.