UNIFORMLY GROWING BACKTRACK TREES

摘要

We consider a general additive weight on a family of non-regularly distributed binary trees introduced by P. W. Purdom for the purpose of modelling backtrack trees. This weight depends on the structure of the subtrees and on weight functions defined on the number of leaves appearing in the tree and its subtrees. Choosing particular weight junctions, the corresponding weight is a characteristic parameter of the tree. We shall derive a general approach to the computation of the average weight for arbitrary weight functions. This general result implies exact and asymptotic expressions for many types of average weights defined on the considered class of trees if the weight functions are arbitrary polynomials in the number of leaves.%Nous considérons un poids additif général sur une famille d'arbres binaires irréguliers introduite par P. W. Purdom dans le but de modéliser des arbres à retours en arrière. Ce poids dépend de la structure des sous-arbres et de fonctions de poids définies sur le nombre de feuilles figurant dans l'arbre et dans ses sous-arbres. Pour un choix particulier de fonctions de poids, le poids correspondant est un paramètre caractéristique de l'arbre. Nous développons une approche générale pour le calcul du poids moyen pour des fonctions de poids arbitraires. Ce résultat général fournit des expressions exactes et asymptotiques pour de nombreux types de poids moyen définis sur la classe d'arbres considérée lorsque les fonctions de poids sont des polynômes quelconques en le nombre de feuilles.