Retour au reportage Retour au reportage
20210159_0046

© Christian MOREL / IRIF / CNRS Images

Référence

20210159_0046

Treillis de Tamari représenté sur des partitions non croisées

Treillis de Tamari représenté sur des partitions non croisées. De nombreuses structures de données se présentent sous la forme d'arbres binaires équilibrées, c'est-à-dire avec toutes ses branches à peu près de la même hauteur. Pour maintenir l'équilibre de ces structures, il est nécessaire d'effectuer un rééquilibrage, appelé rotation, vers la gauche ou la droite. Le treillis de Tamari, introduit par Dov Tamari en 1962 est obtenu en effectuant toutes les rotations possibles vers la droite depuis le peigne gauche. Bien que très étudié, le treillis de Tamari recèle encore bien des mystères à éclaircir, notamment en termes de distance entre deux arbres, qui sont cruciales d'un point de vue algorithmique. Les chercheurs le relient ici aux partitions non croisées.

Délégation(s)

Thématiques scientifiques

CNRS Images,

Nous mettons en images les recherches scientifiques pour contribuer à une meilleure compréhension du monde, éveiller la curiosité et susciter l'émerveillement de tous.