Discussion :

[larchicha]

Bonjour à tous,

Comme le dit le sujet, j'ai trouvé un livre comportant pas mal de questions intéressantes mais difficilement compréhensible.
Je ne tourne pas plus longtemps autour du pot donc voici les Q :

1) Soit h une hauteur, décrivez les AVL de hauteur h ayant le plus de noeuds et le moins de noeuds. Combien y a t'il de noeuds dans ces 2 cas ?

[Mon idée étant que si on part d'un arbre de hauteur h, il y a au minimum n+1 noeuds, et si on remplit totalement l'arbre, on trouve 2^(h+1) - 1 noeuds, maintenant la ou je bloque : la question d'apres nous demande d'en déduire un encadrement de cette hauteur... sachant que la réponse devrait etre : log2(n) <= h <= n - 1 , comment arrive t'on ici ?!!]

[Edit : Je me rends compte que la question traite les AVL, or je parle des ABR en général..:/]

[Graffito]

Si on parle d'AVL (arbres équilibrés) binaires, le nombre de noeuds max est bien égal à 2^(h+1) - 1 - Démonstration facile par récurrence -.
et le nombre de noeud min est évidemment égal à 2^h (nombre max de noeud au niveau h-1 plus un noeud).


Si on parle d'arbre non équilibrés à n noeuds :

• la hauteur max sera égale n -1 (si on considère qu'un arbre à un seul noeud a une hauteur nulle).
• la hauteur min sera celle de l'AVL comportant n noeud (soit la fonction log2(n) inverse des 2^h.

[larchicha]

Merci de ta réponse !
Je sais je réponds 4 ans après , je m'en excuse..