Combinatorics of trees under increasing labellings : asymptotics, bijections and algorithms

Dans cette thèse nous étudions des classes d’arbres étiquetés selon différents modèles d’étiquetages croissants. Ces arbres sont utiles dans la modélisation de nombreux processus. Nous adoptons dans nos recherches différents points de vues complémentaires (combinatoire, probabiliste ou informatique) afin d’enrichir les résultats connus sur les arbres croissants classiques et de proposer de nouvelles classes d’arbres moins contraints que les modèles existants dans la littérature. Nous proposons plusieurs nouveaux modèles d’arbres, dans l’idée de pouvoir représenter un processus d’évolution où l’historique des évolutions est enregistré. Pour ces nouvelles classes d’arbres nous montrons leur liens étroits avec des objets classiques en combinatoire comme les permutations, les partitions d’ensemble, ainsi que les graphes. Nous les étudions également de façon plus détaillée en terme probabiliste pour mieux comprendre la forme typique des grandes structures. Ainsi, nous définissons un processus d’évolution paramétrable qui recouvre ces nouvelles classes d’arbres ainsi que d’autres classes encore plus générales. Cela nous mène à définir plusieurs nouveaux modèles d’étiquetages croissants sur les arbres. Nous réussissons aussi à avoir des formes universelles pour l’énumération asymptotique des classes d’arbres issues de ce processus d’évolution en utilisant notamment des idées empruntées aux sommations de Borel. Du côté algorithmique l’étude des structures arborescentes nécessite la génération et la mémorisation d’arbres de grandes taille ce qui nous mène à élaborer des algorithmes degénération aléatoire uniforme efficaces qui nous permettent de faire des simulations non biaisées sur des arbres de grandes taille. Du fait que nous sommes en mesure d’engendrer des arbres grands, une autre problématique apparaît. Celle-ci concerne leur représentation en mémoire. En particulier, nous nous sommes aperçus qu’une compression efficace serait intéressante afin de manipuler et étudier expérimentalement ces structures arborescentes. Notre étude porte alors sur le taux compression moyen des arbres croissants classiques et elle nous permet de définir une nouvelle structure de données compactifiée pour les arbres binaires de rechercheIn this thesis we study classes of trees labelled according to different increasing labellings.These trees are useful in the modelisation of various processes.In our research different we adopt different but complementary points of view (combinatorial,probabilistic or algorithmic) to enrich the results on classical increasing trees andpropose new tree classes that are less constrained than existing models in the literature.We propose several new tree models, which each represent a process of evolution wherethe histories of evolutions are registered. For these new classes of trees we show their closelinks with classic combinatorial objects such as permutations, set partitions and graphs. Wealso study them in more detail in probabilistic terms to have a better understanding of thetypical shape of large structures.Then, we define a parametrizable evolution process that covers these new classes of treesas well as other even more general classes. This leads us to define several new models ofincreasing labellings on trees. We also derive universal forms for the asymptotic enumerationof tree of classes of trees resulting from this evolution process using, in particular, ideasborrowed from Borel’s summations.On the algorithmic side, the study of tree structures requires the generation and storage oflarge trees. This leads us to develop uniform random generation algorithms which allow us tomake unbiased simulations on large trees. Since we are able to generate large trees, anotherproblem arises concerning their representation in memory. In particular, we have found thatefficient compression would be useful for manipulating and studying experimentally thesetree structures. Our study then focuses on the average compression ratio of increasing treesand it allows us to define a new compacted representation of binary search tree