Arbres binaires équilibrés et treillis de Tamari

Arbres binaires équilibrés et treillis de Tamari

Les arbres binaires de recherche sont des structures de données adaptées pour représenter des ensembles dynamiques totalement ordonnés (voir [AU94], [Knu98], [CLRS03]). Les algorithmes qui résolvent la plupart des questions sur les ensembles dynamiques, comme l’insertion, la sup- pression, ou la recherche d’un élément donné, consomment un temps linéaire en fonction de la hauteur de l’arbre binaire qui l’encode, et si cet arbre binaire est équilibré, ces opérations sont réalisables en temps logarithmique en fonction du cardinal de l’ensemble représenté. Rappelons qu’un arbre binaire est équilibré si pour chacun de ses nœuds x, les hauteurs du sous-arbre gauche et du sous-arbre droit de x diffèrent d’au plus un. L’algorithmique des arbres binaires équilibrés repose essentiellement sur l’opération de rota- tion (la définition de cette opération est rappelée dans le paragraphe 1.3.3 du chapitre 1). Une insertion ou une suppression d’un élément dans un ensemble dynamique totalement ordonné modifie l’arbre binaire qui l’encode et peut dans certains cas le déséquilibrer. L’efficacité de ces algorithmes tient au fait, comme l’on montré Adelson-Velsky et Landis [AVL62], qu’un arbre binaire de recherche ainsi modifié demande au plus deux rotations pour se rééquilibrer, et ce, quelle que soit sa taille.

Étant donné que d’un coté, l’équilibre d’un arbre binaire est maintenu par l’intermédiaire de rotations, et que d’un autre, les arbres binaires sont munis naturellement d’une structure d’ordre partiel induite précisément par les rotations, nous nous proposons dans ce chapitre étudier la question de savoir si les arbres binaires équilibrés jouent un rôle particulier dans le treillis de Tamari. Notre objectif est de combiner ces deux points de vue sur l’opération de rotation : le premier étant algorithmique, et le second, combinatoire. Des expérimentations sur les premiers treillis de Tamari montrent que les intervalles [T, Tsont des arbres binaires équilibrés, sont uniquement constitués d’arbres binaires équilibrés. La démonstration de cette propriété est l’un des résultats principaux de ce chapitre. Comme conséquence, nous donnons une caractérisation de la forme de ces intervalles, et, en utilisant notre notion de grammaire synchrone introduite dans le chapitre 7, nous les dénombrons. Une autre motivation de ce travail, plus algébrique, est justifiée par l’observation suivante. Le produit de deux éléments de la base fondamentale de l’algèbre de Hopf PBT de Loday- Ronco des arbres binaires [LR98], [HNT05] (voir aussi le paragraphe 5.1.3 du chapitre 5) peut s’interpréter comme un intervalle particulier du treillis de Tamari [LR02]. Ainsi, étant donné que l’ensemble des arbres binaires équilibrés est un sous-ensemble de l’ensemble des arbres binaires, et que, en vertu de l’expérimentation précédente, l’ensemble des arbres binaires équilibrés est clos par intervalle dans le treillis de Tamari, il semble naturel de construire une sous-algèbre de Hopf de PBT basée sur les arbres binaires équilibrés. Malheureusement, aucun résultat dans cette direction n’a été obtenu.

Ce chapitre est organisé de la manière suivante. Nous commençons le paragraphe 8.1 par des rappels autour de la notion d’équilibre dans un arbre binaire. Nous établissons ensuite les outils en vue montrer que l’ensemble des arbres binaires équilibrés est clos par intervalle dans le treillis de Tamari. Nous introduisons ensuite dans le paragraphe 8.2 une notion de motif d’arbre binaire, que nous nommons motif de déséquilibre, ainsi qu’une notion d’évitement de motif. Une partition de l’ensemble des arbres binaires équilibrés en trois sous-ensembles suivant la position de leurs éléments dans le treillis de Tamari est proposée, et nous montrons ensuite que les éléments de ces ensembles peuvent être décrits comme les arbres binaires équilibrés qui évitent un certain ensemble de motifs de déséquilibre. Nous construisons également une grammaire synchrone qui engendre les éléments de l’un de ces trois ensembles et obtenons une équation fonctionnelle de point fixe pour la série génératrice qui dénombre ses éléments. Dans le paragraphe 8.3, nous regardons les intervalles d’arbres binaires équilibrés de plus près, et montrons qu’ils sont iso- morphes, en tant que posets, à des hypercubes.

De plus, en encodant les intervalles d’arbres binaires équilibrés par des structures arborescentes particulières, nous construisons une gram- maire synchrone qui les engendre et obtenons par conséquent une équation fonctionnelle de point fixe pour la série génératrice des intervalles d’arbres binaires équilibrés. Nous procédons ensuite de même pour les intervalles maximaux d’arbres binaires équilibrés. Finalement, nous considé- rons dans le paragraphe 8.4 une généralisation des arbres binaires équilibrés et montrons entre autre que l’ensemble des arbres binaires équilibrés est le seul ensemble parmi cette généralisation qui soit à la fois clos par intervalle dans le treillis de Tamari et tel que l’ordre de Tamari réduit à ses éléments possède des intervalles non triviaux. Nous terminons en nous intéressant à trois autres familles d’arbres binaires qui sont closes par intervalle dans le treillis de Tamari, à savoir, les arbres binaires équilibrés en taille, les arbres binaires ayant une canopée fixée et les arbres binaires ayant un indice de Narayana fixé.