Inscription / Connexion Nouveau Sujet
Niveau Prepa intégrée
Partager :

Arbre binaire de recherche

Posté par
matheux14
02-10-22 à 14:33

Bonjour, je sèche complètement sur une démonstration de mon cours de "Stucture de Données Complexes" sur les arbres binaires de recherche.
L'énoncé est le suivant : Si x est la racine d'un sous-arbre à n noeuds, alors l'appel PARCOURS-INFIXE(x) prend un temps \emptyset(n).

Quelqu'un aurait il une idée de comment le démontrer ?

Posté par
GBZM
re : Arbre binaire de recherche 02-10-22 à 15:55

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

Posté par
Ulmiere
re : Arbre binaire de recherche 02-10-22 à 16:22

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

Posté par
matheux14
re : Arbre binaire de recherche 02-10-22 à 22:45

C'est bien  \Theta(n) 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 \Theta(n) 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 \le 3, 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

Posté par
GBZM
re : Arbre binaire de recherche 02-10-22 à 23:29

Pas très clair.

Posté par
matheux14
re : Arbre binaire de recherche 03-10-22 à 12:09

Comment le faire plus rigoureusement ?

Posté par
Ulmiere
re : Arbre binaire de recherche 03-10-22 à 12:12

Citation :
on visite chaque nœud au moins une fois, du coup l'appel PARCOURS-INFIXE(x) prend un temps \Theta(n) puisque l'arbre binaire contient n nœuds


Non, ceci montre seulement que tu fais au moins n opérations, donc un \Omega(n).

Pour l'autre, ton raisonnement me semble un peu foireux en particulier ceci :
Citation :
On peut donc majorer le temps de parcours-infixe d'un noeud par 3


Donc si je suis au sommet de l'arbre et qu'il a 2^{300}-1 noeuds, je fais seulement 3 opérations pour parcourir l'arbre entier ?

Soit C(n) le nombre d'opérations qu'il faut faire lors de l'exécution de PARCOURS-INFIXE lorsque l'argument est un arbre ayant 2^n - 1 noeuds (feuilles et racine incluses), c'est-à-dire un arbre binaire ayant n niveaux de la racine aux feuilles.
On suppose qu'on fait sur sur chaque noeud un nombre u d'opérations.


En utilisant une relation de récurrence que je te laisse chercher, tu peux trouver la valeur exacte de C(n) en fonction de n et de u, et vérifier que c'est un O(2^n) ce qui donne une complexité exponentielle en le nombre de niveaux, mais linéaire en le nombre de noeuds

Posté par
GBZM
re : Arbre binaire de recherche 03-10-22 à 13:41

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.

Posté par
matheux14
re : Arbre binaire de recherche 03-10-22 à 22:57

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 An 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 An + 1 constitué de n + 1 nœuds.

On pose N = n + 1.

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

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

Soit pour An + 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 ?

Posté par
GBZM
re : Arbre binaire de recherche 04-10-22 à 11:18

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).

Arbre binaire de recherche

Posté par
matheux14
re : Arbre binaire de recherche 08-10-22 à 05:44

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 T(n) \in O(n).

Soit la fonction affine :

f(x) = a x + b tel que a, b \neq 0, ~~ \forall x \in \R.

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

Pour n = 0, on a :

T(0) = c

Pour n > 0

T(n) = T(k) + T(n - k - 1) + d

T(n) = (c + d)k + (c + d)(n - k - 1) + d

\boxed{T(n) = (c + d)n + c'} avec c' = -c

Conclusion :

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

T(n) \in O(n)

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).

Posté par
GBZM
re : Arbre binaire de recherche 08-10-22 à 09:07

Tu as recopié le corrigé.

Posté par
matheux14
re : Arbre binaire de recherche 08-10-22 à 10:15

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.

Posté par
ty59847
re : Arbre binaire de recherche 08-10-22 à 10:35

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

Posté par
matheux14
re : Arbre binaire de recherche 08-10-22 à 10:47

Posté par
matheux14
re : Arbre binaire de recherche 09-10-22 à 00:10

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.



Vous devez être membre accéder à ce service...

Pas encore inscrit ?

1 compte par personne, multi-compte interdit !

Ou identifiez-vous :


Rester sur la page

Inscription gratuite

Fiches en rapport

parmi 1580 fiches de maths

Désolé, votre version d'Internet Explorer est plus que périmée ! Merci de le mettre à jour ou de télécharger Firefox ou Google Chrome pour utiliser le site. Votre ordinateur vous remerciera !