Noeuds d'un Tas

[Résolu/Fermé]
Signaler
-
 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.

3 réponses

Messages postés
16408
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
21 octobre 2021
2 900
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+