FONCTIONNELLES ADDITIVES SUR LES ARBRES ALÉATOIRES

FONCTIONNELLES ADDITIVES SUR LES ARBRES ALÉATOIRES

Un arbre discret est un graphe sans cycle, non orienté et connexe (on peut toujours relier deux nœuds de l’arbre par un chemin). Dans la suite, nous allons considérer des arbres enra- cinés et ordonnés. Un arbre est dit enraciné si un nœud est distingué comme étant la racine notée ;. Il est alors possible de décrire un arbre par sa suite des générations : la racine est la génération 0, les voisins de la racine forment la génération 1 et plus généralement, les nœuds à distance k de la racine forment la k-ième génération. Si un nœud u de la génération k a des voisins dans la génération k + 1 alors ces voisins sont appelés les enfants de u. Un arbre est dit ordonné si les enfants de chaque nœud sont munis d’un ordre. Autrement dit, les enfants du nœud u peuvent être ordonnés dans une suite uoù d est le nombre d’enfants de u. Les arbres enracinés et ordonnés sont aussi parfois appelés arbres planaires.On peut coder un arbre planaire fini par des fonctions, voir figure 1.2 (voir par exemple Le Gall [135]). Commençons par la fonction de contour (ou chemin de Dick). Pour cela, rappelons en quoi consiste le parcours d’un arbre en profondeur. Il s’agit de parcourir l’arbre, en partant de la racine ; au temps t = 0, et, arrivé en un nœud u, d’aller vers le premier enfant non visité ui ou alors, si tous les enfants ont déjà été visités, de retourner vers son parent. Le procédé s’arrête lorsqu’on est revenu à la racine en ayant visité tous les enfants de celle-ci. Étant donné que chaque arête est visitée deux fois, il est clair que le temps total d’exploration de l’arbre est 2(jtj 1).

Pour t 2 T, la fonction de contour de t est la fonction C de t 2 T est la suite de générations des individus de t, quand ces individus sont classés dans l’ordre lexicographique. Si t 2 T, on énumère les sommets dans l’ordre lexicographiqueNous commençons par quelques rappels sur les arbres binaires. Le lecteur pourra se référer au livre de Drmota [68], parties 1:2:1 et 1:4:1, Mahmoud [142], chapitre 2 et Sedgewick et Fla- jolet [177], chapitre 6. Ces arbres ont de nombreuses applications notamment en informatique au travers des algorithmes de tri. Ces algorithmes ont été étudiés à la fin des années 1960 et au début des années 1970 par Knuth [126, 128], qui donne des analyses détaillées de plu- sieurs paramètres combinatoires qui permettent de déterminer par exemple leur performance moyenne. Sedgewick [176], quant à lui, s’est intéressé à un des modèles de tri les plus utilisés, l’algorithme Quicksort, qui a été inventé par Hoare au début des années 1960.Le choix uniforme d’un arbre parmi un ensemble d’arbres peut également s’appliquer à d’autres types d’arbres que les arbres binaires. Par analogie, on parlera encore de « modèle de Catalan » à ne pas confondre avec ce qu’on appelle les arbres de Catalan qui sont des arbres planaires.

Dans la suite, il conviendra de faire la distinction entre deux types d’arbres : les arbres non marqués et les arbres marqués. Dans le premier cas, les nœuds des arbres ne contiennent pas d’information et l’on s’intéresse donc simplement à leur forme. Dans le second cas, les arbres sont vus comme des structures de données c’est-à-dire que les nœuds contiennent des informations aussi appelées clés ou marques. Si l’on efface les clés d’un arbre marqué, l’arbre non marqué obtenu est appelé sa forme. Formellement, un arbre marqué est une paire ~t, voir la définition donnée par Neveu [153]. C’est l’ensemble des nœuds de l’arbre marqué.Une des applications les plus importantes des arbres binaires est l’algorithme des arbres binaires de recherche (ABR en abrégé ou encore BST pour « binary search tree » en anglais), voir Mahmoud [142], chapitre 2 ou Chauvin, Clément et Gardy[47], partie 1:2:5. Les ABR sont des structures de données fondamentales en informatique. Ils sont utiles pour classer et chercher des données, appelées des clés. Un ABR à n nœuds internes est un arbre binaire marqué par des clés xprises dans un ensemble totalement ordonné qui satisfait la contrainte que la clé de chaque nœud interne est plus grande que toutes les clés de son sous-arbre de gauche et plus petite que toutes les clés de son sous-arbre de droite. On peut rajouter n + 1 feuilles non étiquetées à cette structure afin d’obtenir un arbre binaire complet marqué à n nœuds internes. Le squelette d’un ABR à n nœuds internes est donc un arbre binaire complet à n nœuds internes et donc n + 1 feuilles et 2n + 1 nœuds.