Q1. Algorithme de génération

On cherche à générer des arbres binaires de manière aléatoire uniformément. Pour cela on utilise une approche basée sur les nombre de Catalan. Cette méthode détermine la probabilité d’avoir k noeuds dans la branche gauche d’un arbre de taille n.

set.seed(42)

On cherche d’abord le nombre d’arbre d’arbres binaires à n noeuds qui est le n-ième nombre de catalan. L’arbre généré sera l’un de ces arbres.

catalan <- function(n) {
  return(factorial(2 * n) / (factorial(n + 1) * factorial(n)));
}

Ensuite, on calcule la probabilité pour un arbre de taille n d’avoir k noeuds à gauche

proba <- function(k, n) {
  if(k >= n)
    return(0);
  return ((catalan(k) * catalan(n - k - 1)) / catalan(n));
}

On utilise la méthode de la transformée inverse pour générer un entier k selon la probabilité proba(k) calculée ci-dessus.

genererK <- function(n) {
  u = runif(1, min = 0, max = 1);
  k = 0;
  s = proba(0, n);
  while(u > s) {
    k = k + 1;
    s = s + proba(k, n);
  }
  return(k);
}

Enfin, à l’aide des fonctions précédentes on génère un arbre binaire de taille n.

genererArbre <- function(n) {
  k = genererK(n);
  if(k == 0) {
    left = NULL;
  }
  else {
    left = genererArbre(k);
  }
  
  if(n - k - 1 == 0) {
    right = NULL;
  }
  else {
    right = genererArbre(n - k - 1);
  }
  
  return(list(leftChild = left, rightChild = right));
}

Q2. Hauteur moyenne

Il parait évident que plus la valeur de n est importante plus sa hauteur a des chances de l’être. Instinctivement, il es difficile de définir une loi mais je suppose que plus n est grand plus il est improbable que sa hauteur soit proche de n ou proche de sa hauteur minimale.

Pour s’aider dans les différentes interprétations, voici une fonction qui calcule la hauteur d’un arbre binaire.

hauteur <- function(a) {
  if(is.null(a) || (is.null(a$leftChild) && is.null(a$rightChild))) {
    return(0);
  } else {
    return(1 + max(hauteur(a$leftChild), hauteur(a$rightChild)));
  }
}

La fonction exemple renvoie un tableau contenant la hauteur de 10 000 arbres de taille n générés à l’aide des fonctions précédentes.

exemple <- function(n) {
  x = c();
  for(i in 1:10000) {
    x[i] = hauteur(genererArbre(n));
  }
  return(x);
}

On effectue différents échantillons: pour n=5

summary(exemple(5))
##    Min. 1st Qu.  Median    Mean 3rd Qu.    Max. 
##   2.000   3.000   3.000   3.238   4.000   4.000

pour n=10

summary(exemple(10))
##    Min. 1st Qu.  Median    Mean 3rd Qu.    Max. 
##    3.00    5.00    6.00    6.08    7.00    9.00

pour n=20

summary(exemple(20))
##    Min. 1st Qu.  Median    Mean 3rd Qu.    Max. 
##    5.00    9.00   10.00   10.31   12.00   18.00

pour n=40

summary(exemple(40))
##    Min. 1st Qu.  Median    Mean 3rd Qu.    Max. 
##    7.00   14.00   16.00   16.46   19.00   31.00

pour n=80

summary(exemple(80))
##    Min. 1st Qu.  Median    Mean 3rd Qu.    Max. 
##   12.00   21.00   25.00   25.32   29.00   50.00

On voit que comme supposé plus haut la taille augmente plus il est rare d’obtenir des hauteurs proches de n. Autrement dit la croissance de la hauteur devient plus faible. En regardant de plus près, on voit que la moyenne et la médiane sont très proches mais aussi que le premier quartile et le troisième sont plus proches de la médiane que du minimum ou maximum. Plus n est grand et plus cette différence se remarque. Les valeurs de la hauteur d’arbres de taille n semblent concentrées autour de la valeur moyenne.

.E(H(n))

Afin de connaitre l’espérance de la hauteur d’un arbre de taille n, on calcule la moyenne des hauteurs d’arbres ayant 1 à N-1 noeuds. On trace la courbe correspondant et également celle représentant la fonction donnée dans l’énoncé. Pour une raison que je n’arrive pas à trouver, le graphe ne s’affiche pas avec le code suivant, il m’est donc impossible de faire plusieurs essais pour trouver les valeurs de c et c’. Je me base donc sur les résultats de mes camarades pour dire que c=-1/2 et c’=-3.

N=10
#je change la valeur dans exemple pour éviter que les calculs soient trop longs
exemple <- function(n) {
  x = c();
  for(i in 1:10) {
    x[i] = hauteur(genererArbre(n));
  }
  return(x);
} 



graph = function()
{
  moy = seq(1,N-1)
  for (i in 1:N-1)
  {
    moy[i] = mean(exemple(i))
  }
  
  racine = 2*sqrt(pi*seq(1,N-1))
  
  logar = log(seq(1,N-1))
  esperance = racine-logar/2 -3
  
  plot(moy, type="l",lwd=1.5, col="red")
  lines(esperance, type="l",lwd=1.5, col="green")

}
#graph()