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.
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.
Discrete mathematics is a discipline with applications to almost all areas of study. It provides a set of indispensable tools to computer science in particular. This course reviews (familiar) topics a
The students learn the theory and practice of basic concepts and techniques in algorithms. The course covers mathematical induction, techniques for analyzing algorithms, elementary data structures, ma
En informatique, un arbre binaire de recherche ou ABR (en anglais, binary search tree ou BST) est une structure de données représentant un ensemble ou un tableau associatif dont les clés appartiennent à un ensemble totalement ordonné. Un arbre binaire de recherche permet des opérations rapides pour rechercher une clé, insérer ou supprimer une clé.
Explore la plus longue sous-séquence commune et les arbres de recherche binaires optimaux, en discutant des algorithmes et des probabilités pour des structures de recherche efficaces.
Couvre la mise en œuvre et les opérations des structures de données de base telles que les piles, les files d'attente et les listes liées, et introduit des arbres de recherche binaires.
In this thesis we present and analyze approximation algorithms for three different clustering problems. The formulations of these problems are motivated by fairness and explainability considerations, two issues that have recently received attention in the ...
EPFL2023
The metric dimension of a graph G is the minimal size of a subset R of vertices of G that, upon reporting their graph distance from a distinguished (source) vertex v⋆, enable unique identification of the source vertex v⋆ among all possible vertices of G. I ...
In the localization game on a graph, the goal is to find a fixed but unknown target node v* with the least number of distance queries possible. In the j-th step of the game, the player queries a single node v_j and receives, as an answer to their query, th ...