Inscription / Connexion Nouveau Sujet
Niveau algorithmique
Partager :

Calculs - Logique

Posté par
johntrump
29-12-15 à 23:09

Bonjour,

On se place dans le cadre des A.B.R., on note :

Calculs - Logique

La hauteur d'un nœud ; le nombre de arrête qu'il faut pour aller du nœud à la racine (1° nœud) dans une arbre binaire de recherche T.

et :

P(T) ; la somme des hauteurs de chaque nœud de l'A.B.R. T.


1) On suppose que T a n nœuds. Estimez P(T) si T est une liste et si T est un arbre binaire de recherche complet.

Si T est une liste ; cela signifie que chaque nœud n'a qu'un fils. Le n° nœud a n-1 arrête, le n-1° a n-2 arrête,..., le 2° nœuds a 1 arrête et 1° nœud (la racine) a 0 arrête, donc P(T) = n-1 + n-2 + ... + 1 + 0 = (n-1)(n-2) / 2.

Maintenant si T est un arbre binaire de recherche complet si les feuilles (un nœud est une feuille s'il n'a aucun fils, dans le dessein ci-dessus, les nœuds qui ont les clés ; 1,4,7 et 13 sont des feuilles) sont toutes à la même hauteur​; là je bloque mais j'ai trouvé :

Le nombre de nœud en fonction du nombre d'étage de T était : n = v(i+1) = 2^(i+1) + v(i) et v(o) = 1 et i est l'étage.

P(T) = u(i+1) = 2^(i+1) * (i+1) + u(i) et u(0) = 0.

Je ne vois pas trop comment estimer P(T) à part idre aussi : P(T) = [n-v(i)](i+1) + u(i) (v(0) = 1 et u(0) = 0).


2) On suppose T un ABR à n nœuds quelconque. Montrer que P(T) = P(T_g) + P(T_d) + (n-1) où T_g est le sous-arbre gauche et T_d le sous-arbre droit.

On a n nœuds : (M_1, M_2,..., M_n) et leur hauteur respective (H_1,H_2,...H_n).

On suppose que T_g contient une partie de (M_1, M_2,..., M_n) \ {M_1°Nœud} et T_d le reste. (Exemple : T_g = (M_1, M_3,..., M_n-1) et T_d = (M_2, M_4,..., M_n))

P(T_g) = (S_1) - 1 + (S_3) - 1 + ... + (S_n-1) - 1.

P(T_d) = (S_2) - 1 + (S_4) - 1 + ... + (S_n) - 1.

P(T_g) + P(T_d) = H_1 + H_2 + ... + H_n - (n-1) = P(T) - (n-1) => P(T) = P(T_g) + P(T_d) + (n-1).


3) On dénote par P(n) la hauteur moyenne d'un ABR T avec n noeuds qui est genere de la facon suivante : on produit une permutation PI de l'ensemble {1,...,n} avec probabilite uniforme et ensuite on insere dans l'arbre vide PI(1),...,PI(n).


Montrer que :

P(n) = 0 si n = 1.

P(n) = 1/n * Somme_i=1,...,n ( P(i-1) + P(n-i) + (n-1) ) si > 1

Je bloque... Une récurrence ?

Posté par
johntrump
re : Calculs - Logique 30-12-15 à 15:35

Pour la 1), c'est :

A la hauteur/étage i on a 2i arrêtes donc leur hauteur (toujours à la hauteur i) est i * 2i ainsi la somme des hauteurs de tout les nœuds d'un ABR complet T est :

P(T) = i=0n i * 2i

Répondre à ce sujet

Seuls les membres peuvent poster sur le forum !

Vous devez être connecté pour poster :

Connexion / Inscription Poster un nouveau sujet
Une question ?
Besoin d'aide ?
(Gratuit)
Un modérateur est susceptible de supprimer toute contribution qui ne serait pas en relation avec le thème de discussion abordé, la ligne éditoriale du site, ou qui serait contraire à la loi.


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

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 !