Deux distributions aléatoires sont appliquées aux arbres binaires à trois sommets, correspondant aux arbres de recherche binaires à trois clés , et . Ces cinq arbres se voient a...
Worldlex WikiContenu en francaisLecture gratuite
Deux distributions aléatoires sont appliquées aux arbres binaires à trois sommets, correspondant aux arbres de recherche binaires à trois clés informatique et en théorie des probabilités , un arbre binaire aléatoire est un arbre binaire sélectionné aléatoirement selon une distribution de probabilités sur les arbres binaires. Différentes distributions ont été utilisées, ce qui confère à ces arbres des propriétés différentes.
D'autres distributions sur les arbres binaires aléatoires incluent la distribution discrète uniforme dans laquelle tous les arbres distincts sont équiprobables, les distributions sur un nombre donné de nœuds obtenues par division répétée, les arbres binaires et les arbres radix pour les données aléatoires, et les arbres de taille variable générés par des processus de branchement .
Pour les arbres aléatoires qui ne sont pas nécessairement binaires, voir arbre aléatoire .
Un arbre binaire étendu, montrant les nœuds internes sous forme de cercles jaunes et les nœuds externes sous forme de carrés rouges.
Un arbre binaire est un arbre enraciné dans lequel chaque nœud peut avoir jusqu'à deux enfants (les nœuds situés directement en dessous de lui dans l'arbre), ces enfants étant désignés comme étant soit à gauche, soit à droite. Il est parfois plus commode de considérer des arbres binaires étendus, dans lesquels chaque nœud est soit un nœud externe sans enfant, soit un nœud interne avec exactement deux enfants. Un arbre binaire non étendu peut être converti en arbre binaire étendu en traitant tous ses nœuds comme internes et en ajoutant un nœud externe pour chaque enfant manquant d'un nœud interne. Réciproquement, un arbre binaire étendu possédant au moins un nœud interne peut être reconverti en arbre binaire non étendu en supprimant tous ses nœuds externes. De cette manière, ces deux formes sont presque entièrement équivalentes pour l'analyse mathématique, à ceci près que la forme étendue autorise un arbre ne comportant qu'un seul nœud externe, ce qui ne correspond à rien dans la forme non étendue. Pour les structures de données informatiques, les deux formes diffèrent, car les nœuds externes de la première forme peuvent être représentés explicitement comme des objets dans une structure de données.
Dans un arbre binaire de recherche, les nœuds internes sont étiquetés par des nombres ou d'autres valeurs ordonnées, appelées clés , agencées de sorte qu'un parcours infixe de l'arbre liste les clés par ordre croissant. Les nœuds externes restent non étiquetés. On peut également étudier les arbres binaires avec tous les nœuds non étiquetés, ou avec des étiquettes non triées. Par exemple, la structure de données des arbres cartésiens utilise des arbres binaires étiquetés qui ne sont pas nécessairement des arbres binaires de recherche.
Un arbre binaire aléatoire est un arbre aléatoire tiré d'une certaine distribution de probabilité sur les arbres binaires. Dans de nombreux cas, ces distributions de probabilité sont définies à partir d'un ensemble de clés donné et décrivent les probabilités que les arbres binaires de recherche possèdent ces clés. Cependant, d'autres distributions sont possibles, ne générant pas nécessairement d'arbres binaires de recherche et ne donnant pas nécessairement un nombre fixe de nœuds.
À partir de permutations aléatoires
Arbre binaire généré à partir d'une permutation aléatoire de 100 éléments
Pour toute séquence de clés ordonnées distinctes, on peut construire un arbre binaire de recherche dans lequel chaque clé est insérée séquentiellement comme une feuille, sans modifier la structure des clés précédemment insérées. La position de chaque insertion est déterminée par une recherche binaire dans l'arbre précédent. Le modèle de permutation aléatoire , pour un ensemble de clés donné, est défini en choisissant la séquence aléatoirement parmi les permutations de cet ensemble, chaque permutation ayant la même probabilité.
Par exemple, si les trois clés 1, 3 et 2 sont insérées dans un arbre binaire de recherche dans cet ordre, le nombre 1 sera à la racine de l'arbre, le nombre 3 sera son enfant droit et le nombre 2 son enfant gauche.
Profondeur attendue d'un nœud
Pour toute clé d'un ensemble donné , la longueur attendue du chemin de la racine à dans un arbre binaire de recherche aléatoire est au plus égale à , où « » désigne la fonction logarithme népérien et le terme introduit la notation grand O. Par linéarité de l'espérance , le nombre attendu d'ancêtres de est égal à la somme, pour toutes les autres clés , des probabilités que soit un ancêtre de . Une clé est un ancêtre de si et seulement si est la première clé insérée dans l'intervalle . Comme chaque clé de l'intervalle a la même probabilité d'être la première, cela se produit avec une probabilité inversement proportionnelle à la longueur de l'intervalle. Ainsi, les clés adjacentes à dans la séquence triée ont une probabilité d'être un ancêtre de , les clés situées à une étape de celle-ci ont une probabilité , etc. La somme de ces probabilités forme deux copies de la série harmonique s'étendant de dans les deux directions à partir de dans la séquence triée, ce qui donne la borne ci-dessus. Cette borne est également valable pour la longueur attendue du chemin de recherche pour une valeur qui est l'une des clés données.
Le chemin le plus long
Le chemin racine-feuille le plus long, dans un arbre binaire de recherche aléatoire, est plus long que la longueur de chemin attendue, mais seulement d'un facteur constant. Sa longueur, pour un arbre à 2 nœuds, est avec une forte probabilité d'environ 2n.
où est le nombre unique dans l'intervalle satisfaisant l'équation
Nombre de feuilles prévu
Dans le modèle de permutation aléatoire, chaque clé, à l'exception de la plus petite et de la plus grande, a une probabilité d'être une feuille de l'arbre. En effet, une clé est une feuille lorsqu'elle est insérée après ses deux voisins, ce qui se produit pour deux des six permutations possibles de cette clé et de ses deux voisins, chacune étant équiprobable. Par un raisonnement similaire, les clés la plus petite et la plus grande ont une probabilité d'être une feuille. Par conséquent, le nombre attendu de feuilles est la somme de ces probabilités, qui est exactement égale à .
Nombre de Strahler
Le nombre de Strahler des sommets d'un arbre mesure la complexité des sous-arbres situés sous ces sommets. Une feuille (nœud externe) a un nombre de Strahler égal à un. Pour tout autre nœud, le nombre de Strahler est calculé récursivement à partir des nombres de Strahler de ses enfants. Dans un arbre binaire, si deux enfants ont des nombres de Strahler différents, le nombre de Strahler de leur parent est le plus grand des deux. En revanche, si deux enfants ont le même nombre de Strahler, celui de leur parent est supérieur de un. Le nombre de Strahler de l'arbre entier est celui du nœud racine. Pour les arbres binaires de recherche aléatoires à n nœuds, les simulations suggèrent que le nombre de Strahler moyen est de l' ordre de 1/2 . Une borne supérieure moins contraignante a été démontrée.
Treaps et arbres binaires de recherche aléatoires
Dans les applications des structures de données d'arbres binaires de recherche, il est rare que les clés soient insérées sans suppression dans un ordre aléatoire, ce qui limite les applications directes des arbres binaires aléatoires. Cependant, les concepteurs d'algorithmes ont élaboré des structures de données qui permettent des insertions et des suppressions arbitraires afin de préserver la propriété selon laquelle la forme de l'arbre est aléatoire, comme si les clés avaient été insérées de manière aléatoire.
Si l'on attribue à un ensemble de clés des priorités numériques (indépendantes de leurs valeurs), ces priorités permettent de construire un arbre cartésien pour ces nombres, c'est-à-dire l'arbre binaire de recherche résultant de l'insertion des clés par ordre de priorité. En choisissant comme priorités des nombres réels aléatoires indépendants compris entre 1 et 1, et en maintenant la structure de l'arbre cartésien par rotation après chaque insertion ou suppression d'un nœud, il est possible de conserver une structure de données se comportant comme un arbre binaire de recherche aléatoire. Une telle structure est appelée « treap » ou arbre binaire de recherche aléatoire.
Les variantes de l'algorithme Treap, notamment l'arbre zip et l'arbre zip-zip, remplacent les rotations d'arbre par des opérations de « zipping » qui divisent et fusionnent les arbres, et qui limitent le nombre de bits aléatoires à générer et à stocker avec les clés. Le résultat de ces optimisations est toujours un arbre à structure aléatoire, mais qui ne correspond pas exactement au modèle de permutation aléatoire.
Arbres binaires aléatoires uniformes
Arbre binaire aléatoire uniforme à 100 nœuds
Le nombre d'arbres binaires à nœuds est un nombre de Catalan . Pour ces nombres d'arbres,
Ainsi, si l'un de ces arbres est sélectionné uniformément au hasard, sa probabilité est l' inverse d'un nombre de Catalan. Les arbres générés à partir d'un modèle suivant cette distribution sont parfois appelés arbres catalans binaires aléatoires . Leur profondeur attendue est proportionnelle à la racine carrée de n , et non à son logarithme . Plus précisément, la profondeur attendue d'un nœud choisi aléatoirement dans un arbre à n nœuds de ce type est de n/2.
.
Le nombre de Strahler attendu d'un arbre binaire à nœuds aléatoire uniforme est inférieur au nombre de Strahler attendu des arbres binaires de recherche aléatoires.
Du fait de leur grande hauteur, ce modèle d'arbres aléatoires équiprobables n'est généralement pas utilisé pour les arbres binaires de recherche. Il a cependant d'autres applications, notamment :
Modélisation des réseaux fluviaux , l'application originale pour laquelle le nombre de Strahler a été développé.
Modélisation des arbres évolutifs possibles pour un nombre fixe d'espèces. Dans cette application, un arbre binaire étendu est utilisé, les espèces se trouvant à ses nœuds externes.
Un algorithme de Jean-Luc Rémy génère un arbre binaire uniformément aléatoire de taille spécifiée en un temps linéaire par rapport à la taille, selon le processus suivant : on part d’un arbre constitué d’un seul nœud externe. Tant que l’arbre n’a pas atteint la taille cible, on choisit aléatoirement et uniformément l’un de ses nœuds (interne ou externe). On remplace le nœud choisi par un nouveau nœud interne, dont l’un des enfants (à gauche ou à droite, indifféremment) est le nœud choisi, et l’autre enfant est un nouveau nœud externe. L’algorithme s’arrête lorsque la taille cible est atteinte.
Processus de branchement
Le processus de Galton-Watson décrit une famille de distributions sur les arbres dans laquelle le nombre d'enfants de chaque nœud est choisi aléatoirement, indépendamment des autres nœuds. Pour les arbres binaires, deux versions du processus de Galton-Watson sont utilisées, qui diffèrent uniquement par la possibilité d'inclure ou non un arbre binaire étendu ne comportant qu'un seul nœud, la racine externe :
Dans la version où le nœud racine peut être externe, il est choisi comme interne avec une certaine probabilité ou externe avec une probabilité donnée . S'il est interne, ses deux enfants sont des arbres générés récursivement par le même processus.
Dans la version où le nœud racine doit être interne, ses enfants gauche et droit sont déterminés comme étant internes avec une certaine probabilité ou externes avec une autre
Les arbres ainsi générés sont appelés arbres binaires de Galton-Watson . Dans le cas particulier où ils sont appelés arbres binaires critiques de Galton-Watson .
Analyse
Cette probabilité marque une transition de phase pour le processus binaire de Galton-Watson : pour , l’arbre résultant est presque certainement fini, tandis que pour , il est infini avec une probabilité positive. Plus précisément, pour \ frac12" { frac {1}{2
.
Une autre façon de générer les mêmes arbres consiste à effectuer une séquence de lancers de pièces , avec une probabilité de pile et une probabilité de face, jusqu'au premier lancer où le nombre de faces dépasse le nombre de piles (pour le modèle dans lequel une racine externe est autorisée) ou dépasse un plus le nombre de piles (lorsque la racine doit être interne), puis à utiliser cette séquence de lancers de pièces pour déterminer les choix effectués par le processus de génération récursive, en ordre de profondeur d'abord.
Puisque le nombre de nœuds internes est égal au nombre de faces obtenues lors de ce lancer de pièce, tous les arbres ayant un nombre donné de nœuds sont générés à partir de séquences de lancers de pièce (uniques) de même longueur et sont équiprobables, quelle que soit la valeur de . Autrement dit, le choix de influence la variation de la taille des arbres générés par ce processus, mais pour une taille donnée, les arbres sont générés uniformément et aléatoirement. Pour des valeurs de inférieures à la attendue plus petite , tandis que des valeurs plus grandes de produiront des arbres de taille attendue plus grande. À la probabilité critique , il n'y a pas de borne finie sur la taille attendue des arbres générés par ce processus. Plus précisément, pour série géométrique
tout arbre particulier avec des nœuds internes est généré avec une
.
Applications
Les processus de Galton-Watson ont été initialement développés pour étudier la diffusion et l'extinction des noms de famille humains et ont été largement appliqués, de manière plus générale, à la dynamique des populations humaines et animales. Ces processus ont été généralisés à des modèles où la probabilité d'appartenir à un nœud interne ou externe à un niveau donné de l'arbre (une génération , dans le cadre de la dynamique des populations ) n'est pas fixe, mais dépend du nombre de nœuds au niveau précédent. Une version de ce processus, avec la a été étudiée comme modèle de spéciation , où elle est connue sous le nom de processus de ramification critique . Dans ce processus, chaque espèce a une durée de vie distribuée exponentiellement et, au cours de sa vie, produit des espèces filles à un taux égal à sa durée de vie. Lorsqu'une espèce fille est produite, l'espèce mère continue comme branche gauche de l'arbre phylogénétique et l'espèce fille devient la branche droite.
Une autre application des arbres critiques de Galton-Watson (dans la version où la racine doit être interne) apparaît dans l' algorithme de Karger-Stein pour la recherche de coupes minimales dans les graphes, utilisant un processus de contraction récursive des arêtes . Cet algorithme s'appelle lui-même deux fois récursivement, chaque appel ayant une probabilité d'au moins 1/2 de préserver la solution correcte. L'arbre aléatoire modélise le sous-arbre des appels récursifs corrects. L'algorithme réussit sur un graphe à n sommets lorsque cet arbre aléatoire d'appels récursifs corrects possède une branche de profondeur au moins 1/2 atteignant le cas de base de sa récursion. La probabilité de succès
Processus de Noël
Devroye et Robson considèrent un processus aléatoire continu apparenté, dans lequel chaque nœud externe est finalement remplacé par un nœud interne possédant deux enfants externes, après un délai exponentiellement distribué suivant sa première apparition en tant que nœud externe. Le nombre de nœuds externes dans l'arbre, à tout instant, est modélisé par un processus de naissance simple , ou processus de Yule, où les membres d'une population se reproduisent à un rythme constant : la naissance d'un enfant, dans le processus de Yule, correspond à son remplacement par deux enfants, dans le modèle de Devroye et Robson. Si ce processus est arrêté à un instant donné, on obtient un arbre binaire de taille aléatoire (dépendant de l' instant d'arrêt ), distribuée selon le modèle de permutation aléatoire pour cette taille. Devroye et Robson utilisent ce modèle dans un algorithme permettant de générer rapidement des arbres selon le modèle de permutation aléatoire, décrits par le nombre de nœuds à chaque profondeur plutôt que par leur structure exacte. Une variante discrète de ce processus commence par un arbre constitué d'un seul nœud externe, et remplace de manière itérative un nœud externe choisi aléatoirement par un nœud interne ayant deux enfants externes. De même, si ce processus est arrêté à un instant donné (pour une taille donnée), l'arbre résultant est distribué selon le modèle de permutation aléatoire correspondant à cette taille.
Essais binaires
Un trie binaire et un arbre radix représentent les mêmes données : huit nombres compris entre 1 et 1. Les étiquettes sont les préfixes des représentations binaires des nombres, partagés par au moins deux d'entre eux.
Une autre forme d'arbre binaire, le trie binaire ou arbre de recherche numérique, utilise une collection de nombres binaires pour étiqueter certains de ses nœuds externes. Les nœuds internes de l'arbre représentent des préfixes de leurs représentations binaires partagés par au moins deux nombres. Les enfants gauche et droit d'un nœud interne sont obtenus en étendant le préfixe correspondant d'un bit supplémentaire : un zéro ou un un, respectivement. Si cette extension ne correspond à aucun des nombres donnés, ou si elle ne correspond qu'à un seul d'entre eux, le résultat est un nœud externe ; sinon, il s'agit d'un autre nœud interne. Des tries binaires aléatoires ont été étudiés, par exemple pour des ensembles de nombres réels aléatoires générés indépendamment dans l' intervalle [0, 1] . Bien que ces arbres puissent comporter des nœuds externes vides, ils tendent à être mieux équilibrés que les arbres de recherche binaires aléatoires. Pour des nombres réels uniformément aléatoires dans l'intervalle [0, 1], ou plus généralement pour toute distribution de probabilité de carré intégrable sur l'intervalle [0, 1], la profondeur moyenne d'un nœud est asymptotiquement ∂²/∂t et la hauteur moyenne de l'arbre entier est asymptotiquement ∂²/∂t . L'analyse de ces arbres peut être appliquée à la complexité de calcul des algorithmes de tri basés sur les tries .
Une variante du trie, l' arbre radix ou trie compressé, élimine les nœuds externes vides et leurs nœuds internes parents. Les nœuds internes restants correspondent à des préfixes pour lesquels les deux extensions possibles, par un bit zéro ou un, sont utilisées par au moins un des nombres choisis aléatoirement. Pour un arbre radix de nombres binaires uniformément distribués, le chemin feuille-racine le plus court a une longueur et le chemin feuille-racine le plus long a une longueur, les deux étant très probables .
arbres de division aléatoire
Luc Devroye et Paul Kruszewski décrivent un processus récursif de construction d'arbres binaires aléatoires . Ce processus génère une variable aléatoire réelle dans l'intervalle [0, 1] , assigne les premiers nœuds (arrondis à l'entier inférieur) au sous-arbre gauche, le nœud suivant à la racine et les nœuds restants au sous-arbre droit. Il se poursuit ensuite récursivement en appliquant le même processus aux sous-arbres gauche et droit. Si la variable aléatoire est choisie uniformément au hasard dans l'intervalle [0, 1], le résultat est identique à celui d'un arbre binaire de recherche aléatoire généré par une permutation aléatoire des nœuds, car chaque nœud a la même probabilité d'être choisi comme racine. Cependant, cette formulation permet d'utiliser d'autres distributions. Par exemple, dans le modèle d'arbre binaire uniformément aléatoire, une fois la racine fixée, chacun de ses deux sous-arbres doit également être uniformément aléatoire. Ainsi, le modèle uniformément aléatoire peut aussi être généré par un choix différent de distribution (dépendant de la valeur de la variable aléatoire ) . Comme ils le montrent, en choisissant une distribution bêta et en utilisant une forme appropriée pour dessiner chacune des branches, les arbres mathématiques générés par ce processus peuvent être utilisés pour créer des arbres botaniques d'apparence réaliste.
Worldlex Wiki 
{ frac {1}{2 