6.4 Formes d’arbres binaires de recherche biaisées
257
de recherche constituent un processus d’arbres bourgeonnants. C’est ce processus
que nous allons « biaiser » de la façon suivante. Définissons par récurrence sur n un
nouveau processus ( τ n ) n≥0 d’arbres dits biaisés ou colorés. Soit z un paramètre réel
strictement positif.
(i) τ 0 est une feuille rose ;
(ii) τ 1 est :
– avec probabilité
1
2 , un noeud racine rose avec une feuille gauche noire et
une feuille droite rose,
– avec probabilité
1
2 , un noeud racine rose avec une feuille gauche rose et une
feuille droite noire ;
(iii) par récurrence, si τ n est un arbre binaire complet avec n nœuds internes, une
épine dorsale de nœuds roses, les autres nœuds internes noirs, une feuille
rose au bout de l’épine dorsale et les n autres feuilles noires, alors z étant
un paramètre réel positif fixé, l’arbre τ n pousse avec la règle suivante :
– avec probabilité
1
n + 2z
, une feuille noire est choisie, et cette feuille noire
est remplacée par un nœud noir et deux feuilles noires ;
– avec probabilité
z
n + 2z
, la feuille rose est choisie, et elle est remplacée par
un nœud rose ayant une feuille gauche noire et une feuille droite rose ;
– avec probabilité
z
n + 2z
, la feuille rose est choisie et elle est remplacée par
un nœud rose ayant une feuille gauche rose et une feuille droite noire.
La figure 6.11 illustre ce processus ; un arbre biaisé de taille 6 est d’abord
représenté, puis l’arbre de taille 7 qui en résulte par choix d’une feuille noire, et
les deux autres possibles (aussi de taille 7) par choix de la feuille rose.
Appelons P z la loi de l’arbre coloré de paramètre z. Remarquons que pour le
paramètre z =
1
2 , nous retrouvons le modèle de l’arbre bourgeonnant habituel sans
couleurs, et donc
P 1
2
= P,
où P est la loi de l’arbre bourgeonnant habituel. Nous nous intéressons à
s n := niveau de la feuille rose.
Au début, s 0 = 0, s 1 = 1 mais ensuite s n est aléatoire. Nous allons voir que
s n = s 0 + (s 1 − s 0 ) + · · · + (s n − s n−1 )
est une marche aléatoire dont les pas s k − s k−1 sont indépendants mais pas de même
loi. En effet, s n+1 − s n vaut 1 quand la feuille rose est choisie, donc avec probabilité
2z
n+2z , et vaut 0 sinon. Autrement dit, les pas s n+1 − s n sont indépendants, de loi de
257
de recherche constituent un processus d’arbres bourgeonnants. C’est ce processus
que nous allons « biaiser » de la façon suivante. Définissons par récurrence sur n un
nouveau processus ( τ n ) n≥0 d’arbres dits biaisés ou colorés. Soit z un paramètre réel
strictement positif.
(i) τ 0 est une feuille rose ;
(ii) τ 1 est :
– avec probabilité
1
2 , un noeud racine rose avec une feuille gauche noire et
une feuille droite rose,
– avec probabilité
1
2 , un noeud racine rose avec une feuille gauche rose et une
feuille droite noire ;
(iii) par récurrence, si τ n est un arbre binaire complet avec n nœuds internes, une
épine dorsale de nœuds roses, les autres nœuds internes noirs, une feuille
rose au bout de l’épine dorsale et les n autres feuilles noires, alors z étant
un paramètre réel positif fixé, l’arbre τ n pousse avec la règle suivante :
– avec probabilité
1
n + 2z
, une feuille noire est choisie, et cette feuille noire
est remplacée par un nœud noir et deux feuilles noires ;
– avec probabilité
z
n + 2z
, la feuille rose est choisie, et elle est remplacée par
un nœud rose ayant une feuille gauche noire et une feuille droite rose ;
– avec probabilité
z
n + 2z
, la feuille rose est choisie et elle est remplacée par
un nœud rose ayant une feuille gauche rose et une feuille droite noire.
La figure 6.11 illustre ce processus ; un arbre biaisé de taille 6 est d’abord
représenté, puis l’arbre de taille 7 qui en résulte par choix d’une feuille noire, et
les deux autres possibles (aussi de taille 7) par choix de la feuille rose.
Appelons P z la loi de l’arbre coloré de paramètre z. Remarquons que pour le
paramètre z =
1
2 , nous retrouvons le modèle de l’arbre bourgeonnant habituel sans
couleurs, et donc
P 1
2
= P,
où P est la loi de l’arbre bourgeonnant habituel. Nous nous intéressons à
s n := niveau de la feuille rose.
Au début, s 0 = 0, s 1 = 1 mais ensuite s n est aléatoire. Nous allons voir que
s n = s 0 + (s 1 − s 0 ) + · · · + (s n − s n−1 )
est une marche aléatoire dont les pas s k − s k−1 sont indépendants mais pas de même
loi. En effet, s n+1 − s n vaut 1 quand la feuille rose est choisie, donc avec probabilité
2z
n+2z , et vaut 0 sinon. Autrement dit, les pas s n+1 − s n sont indépendants, de loi de