Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur GraphSearch.
Concept
Algorithme de Rémy
Résumé
L'algorithme de Rémy est un générateur d'arbres binaires, dont la principale application est un algorithme efficace de génération aléatoire d'arbres binaires.
L'algorithme doit son nom à son inventeur Jean-Luc Rémy.
L'algorithme de Rémy est dû à Jean-Luc Rémy, chercheur au Centre de recherche en informatique de Nancy. Il a été créé en 1978 sans être publié immédiatement et a fait partie du folklore de l'algorithmique et de la combinatoire énumérative jusqu'à sa parution dans une revue francophone en 1985.
Les arbres binaires sont dénombrés par les nombres de Catalan donnés par les formules de récurrence :
Mais ces formules ne permettent pas de dériver un algorithme efficace de génération aléatoire.
L'idée de Rémy consiste à non plus compter les arbres binaires à nœuds, mais les arbres binaires décorés à nœuds, à savoir les arbres dont les feuilles ont été décorées par les nombres de à dans un ordonnancement quelconque. Il y a manières de décorer un arbre binaire, par conséquent, le nombre d'arbres binaires à nœuds internes est
Comme le note Knuth, Olinde Rodrigues avait déjà démontré cette formule, en 1838, dans un article du Journal de Liouville. On note au passage que cela correspond à la récurrence linéaire sur les nombres de Catalan :
Rémy a remarqué qu'il y a moyens de construire un arbre décoré de taille à partir d'un arbre décoré de taille . On choisit un nœud interne ou externe (une feuille) dans cet arbre, appelons le . Comme il y a nœuds internes et feuilles, il y a choix possibles de . On insère alors un nouveau nœud interne et une nouvelle feuille décorée par , dont elle est la fille droite ou la fille gauche, tandis que en est alors le fils gauche ou le fils droit, comme cela est illustré dans les dessins ci-dessous.
Remy x left.png| x à gauche
Remy x right.png|x à droite
La suite d'arbres ci-dessus illustre des insertions de nœuds conduisant à la construction d'un arbre binaire de taille .
On voit que ce processus est unique ; en effet, l'insertion peut être inversée par la coupe de la feuille de plus grand numéro.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.