BINARY TREES, FRINGE THICKNESS AND MINIMUM PATH LENGTH

摘要

We solve the following problem: Characterize the minimum-path-length binary trees with respect to size and fringe thickness, where the fringe thickness of a tree is the difference between the lengths of shortest and longest root-to-frontier paths. This result demonstrates that minimum path length is, in this setting, more amenable to analysis than maximum path length.%Nous résolvons le problème suivant : caractériser les arbres binaires de longueur de chemins minimum pour une taille et une épaisseur de frange données, où l'épaisseur de la frange est égale à la différence entre les longueurs d'un plus court et d'un plus long chemin de la racine à la frontière. Ce résultat démontre que, dans ce contexte, la longueur minimale d'un chemin se prêle mieux à l'analyse que la longueur maximale.