Noeuds d'un Tas
Résolu
ploc
-
ploc -
ploc -
Bonsoir,
je ne comprends pas pourquoi le nombre de noeuds minimum d'un tas de hauteur h est 2^h et le nombre de noeuds maximum est 2^(h+1) - 1
Merci de bien vouloir m'éclairer.
je ne comprends pas pourquoi le nombre de noeuds minimum d'un tas de hauteur h est 2^h et le nombre de noeuds maximum est 2^(h+1) - 1
Merci de bien vouloir m'éclairer.
3 réponses
-
Bonjour,
Un tas est forcément complet sur chaque ligne (sauf la dernière)
Donc au maximum sur la première ligne tu as 1=2^0 noeud, la deuxième 2=2^1, troisième 4=2^2, ... ligne h : 2^h noeuds.
Si on fait la somme ça donne 2^(h+1)-1
Quant au minimum, ça se déduit du maximum. Si ton tas de hauteur h est complet avec 2^(h+1)-1 noeuds, alors tu rajoutes 1 noeud, et ça te donne le plus petit tas possible de hauteur h+1 avec 2^(h+1) noeuds -
Hello,
putain, c'est loin celà !
Un peu de révisions :
https://rmdiscala.developpez.com/cours/LesChapitres.html/Cours4/Chap4.7.htm
A+
-
