Bonjour,

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



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 ?