{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Arbres binaires aléatoires"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Marc Lorenzi - 24 avril 2018"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import matplotlib.pyplot as plt\n",
    "%matplotlib inline\n",
    "import random\n",
    "from math import sqrt, pi"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Il existe un certain nombre de méthodes pour créer des arbres binaires aléatoires avec une probabilité uniforme. Un certain nombre d'entre-elles reposent sur une numérotation des arbres binaires à $n$ noeuds et ont pour inconvénient de devoir manipuler des entiers exponentiels en $n$. En effet, le nombre d'arbres binaires à $n$ noeuds est le $n$ième nombre de Catalan $C_n=\\frac 1 {n+1}\\binom{2n}n$. La méthode présentée ici est au contraire linéaire en $n$. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 1. Parenthésages bien formés"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Cette présentation s'inspire de l'article de Atkinson et Sak, \"Generating binary trees at random\" (Information Processing Letters 41, North-Holland 1992). Les résultats donnés ici sont démontrés dans l'article en question."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "On pose $\\mathcal A=\\{+, -\\}$. On note $\\mathcal L = \\mathcal A^*$ le langage des mots sur l'alphabet $\\mathcal A$, c'est à dire des suites finies de \"$+\"$ et de \"$-$\". Les symboles $+$ et $-$ représentent respectivement la parenthèse ouvrante et la parenthèse fermante, et un mot de $\\mathcal L$ est donc une suite de parenthèses. Le choix de $+$ et de $-$ m'a semblé un bon choix concernant la lisibilité.\n",
    "\n",
    "__Définition__ : Le __poids__ de la lettre $+$ vaut 1, celui de la lettre $-$ vaut $-1$. Le poids $\\mu(w)$ d'un mot $w$ est la somme des poids de ses lettres.\n",
    "\n",
    "La fonction poids $\\mu:\\mathcal L \\to \\mathbb Z$ est un morphisme de monoïdes de $\\mathcal L$ muni du produit des mots vers $\\mathbb Z$ muni de l'addition.\n",
    "\n",
    "__Notation__ : On note $|w|$ la longueur du mot $w$. Pour toute lettre $a\\in\\mathcal A$, on note $|w|_a$ le nombre d'occurences de la lettre $a$ dans le mot $w$.\n",
    "\n",
    "__Définition__ : Un mot $w$ est __équilibré__ lorsque $|w|_+ = |w|_-$. Bien entendu un mot est équilibré ssi son poids est nul. Et tout aussi bien entendu, la longueur d'un mot équilibré est paire.\n",
    "\n",
    "Les fonctions $w\\mapsto |w|$ et $w\\mapsto |w|_a$ sont des morphismes de monoïdes de $\\mathcal L$ muni du produit des mots vers $\\mathbb N$ muni de l'addition.\n",
    "\n",
    "__Notation__ : $\\mathcal E\\subset \\mathcal L$ est l'ensemble des mots équilibrés. On note également, pour tout entier $n$, $\\mathcal E_n=\\{w\\in \\mathcal E, |w|=2n\\}$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.1 Parenthésages aléatoires"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "La fonction ci-dessous choisit $k$ objets dans une liste $s$ ($k\\le |s|$). Pour cela, elle effectue une permutation aléatoire de la liste et renvoie les $k$ premiers éléments. L'algorithme utilisé est une version modifiée de l'algorithme de Fisher-Yates effectuant le mélange d'une liste."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def choose(k, s):\n",
    "    n = len(s)\n",
    "    for i in range(k):\n",
    "        j = random.randint(i, n - 1)\n",
    "        s[j], s[i] = s[i], s[j]\n",
    "    return s[:k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "choose(5, list(range(100)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "La fonction `random_balanced_word` renvoie un mot aléatoire équilibré de $\\mathcal E_n$ avec une probabilité uniforme."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def random_balanced_word(n):\n",
    "    s = choose(n, list(range(2 * n)))\n",
    "    p = (2 * n) * ['+']\n",
    "    for k in range(n):\n",
    "        p[s[k]] = '-'\n",
    "    w = ''\n",
    "    for k in range(2 * n):\n",
    "        w = w + p[k]\n",
    "    return w"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "random_balanced_word(20)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Proposition__ : la fonction `random_balanced_word` renvoie un mot équilibré de longueur $2n$ avec une probabilité uniforme."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.2 Défaut d'un mot équilibré"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Le poids d'un mot $w$ est la somme $\\mu(w)$ des poids de ses lettres, où l'on a posé $\\mu(+)=1$ et $\\mu(-)=-1$. La fonction `poids_partiels` prend un mot en paramètre et renvoie la liste des poids de ses préfixes.  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def poids_partiels(w):\n",
    "    s = [0]\n",
    "    mu = 0\n",
    "    for c in w:\n",
    "        if c == '+': mu += 1\n",
    "        else: mu -= 1\n",
    "        s.append(mu)\n",
    "    return s"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "La fonction `plot_paren` affiche la représentation graphique de la liste renvoyée par `poids_partiels`. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def plot_paren(s):\n",
    "    n = len(s)\n",
    "    ws = poids_partiels(s)\n",
    "    plt.plot(ws, 'k')\n",
    "    plt.plot((n + 1) * [0], 'r')\n",
    "    plt.grid()\n",
    "    plt.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "plot_paren(random_balanced_word(10))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Pour un mot équilibré $w$, le graphique obtenu est une courbe en zigzag commençant et finissant sur l'axe des abscisses. Le nombre de segments au-dessous de l'axe des $x$ est un nombre paire, $2i$. L'entier $i$ est appelé le __défaut__ de $w$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def defaut(w):\n",
    "    mu = poids_partiels(w)\n",
    "    c = 0\n",
    "    for i in range(len(mu)  - 1):\n",
    "        if mu[i] <= 0 and mu[i + 1] <= 0: c += 1\n",
    "    return c // 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "s = random_balanced_word(10)\n",
    "plot_paren(s)\n",
    "print(defaut(s))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Pour $i=0,\\ldots,n$ notons $\\mathcal E_{ni}$ l'ensemble des mots équilibrés de défaut $i$. Les $\\mathcal E_{ni}$ forment une partition de $E_n$. Il s'avèrent que ces ensembles sont tous de même cardinal."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.4 Mots bien formés"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Définition__ : Un mot $w$ est dit __bien formé__ lorsqu'il est équilibré et de défaut nul, c'est à dire lorsqu'il appartient à $\\mathcal E_{n0}$.\n",
    "\n",
    "Un mot $u$ est bien formé lorsqu'il correspond à un parenthésage licite. Prenons par exemple l'expression $((x+y))+(x+y+((z)))$. Enlevons les lettres, il reste $(())((()))$. Le mot $++--+++---$ est un mot bien formé.\n",
    "\n",
    "__Notation__ : On note $\\mathcal F\\subset \\mathcal E$ l'ensemble des mots bien formés et $\\mathcal F_n=\\mathcal E_{n0}$ l'ensemble des mots bien formés de longueur $2n$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "weight = {'+': 1, '-': -1}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def well_formed(w):\n",
    "    c = 0\n",
    "    for k in range(len(w)):\n",
    "        c = c + weight[w[k]]\n",
    "        if c < 0: return False\n",
    "    return c == 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "w = '+-++--'\n",
    "plot_paren(w)\n",
    "well_formed(w)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "w = '++---+'\n",
    "plot_paren(w)\n",
    "well_formed(w)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.5 Découpage d'un mot"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Notation__ : pour tout mot $w$, $w^*$ désigne le mot $w$ dans lequel on a échangé les $+$ et les $-$. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "oppose = {'+':'-', '-':'+'}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def star(w):\n",
    "    w1 = ''\n",
    "    for c in w:\n",
    "        w1 = w1 + oppose[c]\n",
    "    return w1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "star('+--+--')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "L'application $\\mapsto w^*$ est un endomorphisme du monoïde $\\mathcal L$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Définition__ : Soit $w\\in\\mathcal E$ un mot équilibré. On dit que $w$ est __réductible__ lorsque $w=uv$ pù $u$ et $v$ sont équilibrés et non vides. Sinon on dit que $w$ est __irréductible__.\n",
    "\n",
    "Clairement, un mot équilibré et non vide est irréductible si et seulement si aucun des ses préfixes propres n'est de poids nul. Ce qui équivaut encore à dire que tous ses préfixes propres sont de poids strictement positif ou bien tous ses préfixes propres sont de poids strictement négatif."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Proposition__ : Si un mot équilibré $w$ est irréductible, alors l'un des deux mots $w$ et $w^*$ est bien formé. Plus précisément, $w=+u-$ où $u$ est bien formé, ou bien $w=-u+$ où $u^*$ est bien formé. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Proposition__ : Tout mot $w$ équilibré s'écrit de façon unique comme un produit $w=w_1w_2\\ldots w_n$ de mots irréductibles. Le mot $w$ est bien formé si et seulement si les $w_i$ le sont aussi."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "La fonction `cut` prend en paramètre un mot $w$ supposé équilibré. Elle renvoie un couple $(u, v)$ tel que $w=uv$ et u est irréductible.\n",
    "\n",
    "Des appels successifs à `cut` permettent de décomposer $w$ en produit de mots irréductibles."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def cut(w):\n",
    "    k = 1\n",
    "    p = weight[w[0]]\n",
    "    while k < len(w) and p != 0:\n",
    "        p = p + weight[w[k]]\n",
    "        k = k + 1\n",
    "    return (w[:k], w[k:])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "w = random_balanced_word(10)\n",
    "print(w)\n",
    "print(cut(w))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "La fonction `decomposer` prend en paramètre un mot `w` supposé équilibré. Elle renvoie la décomposition du mot $w$ en produit de mots irréductibles."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def decomposer(w):\n",
    "    if len(w) == 0: return []\n",
    "    else:\n",
    "        u, v = cut(w)\n",
    "        us = decomposer(v)\n",
    "        return [u] + us"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "w = random_balanced_word(30)\n",
    "print(w)\n",
    "print(decomposer(w))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.6 Création de mots bien formés"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "La fonction $\\varphi : \\mathcal E \\to \\mathcal F$ est définie par induction structurelle sur les mots.\n",
    "\n",
    "- $\\varphi(\\varepsilon)=\\varepsilon$, le mot vide.\n",
    "-  Pour tout $w\\in\\mathcal E\\setminus\\{\\varepsilon\\}$, on écrit $w=uv$ où $u$ est irréductible.\n",
    "\n",
    "    - Si $u\\in\\mathcal F$, $\\varphi(w)=u\\varphi(v)$.\n",
    "    - Sinon, $u=-t+$ où $t^*\\in\\mathcal F$, et $\\varphi(w)=+\\varphi(v)-t^*$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def phi(w):\n",
    "    if len(w) == 0: return ''\n",
    "    else:\n",
    "        u, v = cut(w)\n",
    "        v1 = phi(v)\n",
    "        if well_formed(u): return u + v1\n",
    "        else:\n",
    "            return '+' + v1 + '-' + star(u[1:-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def random_well_formed_word(n):\n",
    "    return phi(random_balanced_word(n))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "w = random_well_formed_word(500)\n",
    "print(w)\n",
    "print(well_formed(w))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "w = random_well_formed_word(1000)\n",
    "plot_paren(w)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Proposition__ : $\\varphi:\\mathcal E_{ni}\\to\\mathcal F_n$ est une bijection."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Proposition__ : $\\varphi:\\mathcal E_n\\to\\mathcal F_n$ est surjective. Mieux, tout mot de $\\mathcal F_n$ a exactement $n+1$ antécédents par $\\varphi$, un dans chacun des $\\mathcal E_{ni}, i=0,\\ldots,n$. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Proposition__ : Soit $X:\\Omega\\to \\mathcal E_n$ une variable aléatoire suivant une loi uniforme. Alors $\\phi(X):\\Omega \\to\\mathcal F_n$ suit une loi uniforme. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.7 Bilan"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Nous disposons d'un algorithme renvoyant un mot bien formé aléatoire de longueur $2n$ avec une loi uniforme. Nous allons maintenant établir une bijection entre les mots bien formés de $\\mathcal F_n$ et les arbres binaires à $n$ noeuds internes. La composition de notre algorithme avec la bijection fournira ainsi un algorithme renvoyant un arbre binaire aléatoire à $n$ noeuds avec une loi uniforme."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2. Arbres binaires aléatoires"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "On s'intéresse uniquement à la forme des arbres binaires, et pas à la valeur de leurs noeuds. Un arbre est soit vide (nous noterons $e$ l'arbre vide), soit un couple $(t_1, t_2)$ où $t_1$ et $t_2$ sont eux-mêmes des arbres.\n",
    "\n",
    "On note $\\mathcal T$ l'ensemble des arbres binaires et, pour tout entier $n$, $\\mathcal T_n$ l'ensemble des arbres binaires à $n$ noeuds (internes). \n",
    "\n",
    "Nous représenterons l'arbre vide en Python par l'entier 0 (choix arbitraire, encore une fois dicté par des considérations de lisibilité)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "empty_tree = 0\n",
    "def node(t1, t2): return (t1, t2)\n",
    "\n",
    "def left(t): return t[0]\n",
    "def right(t): return t[1]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.1 Conversions entre mots bien formés et arbres binaires"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Soit $\\psi:\\mathcal F\\to\\mathcal T$ la fonction définie comme suit. Soit $w\\in\\mathcal F$ un mot bien formé. Tout d'abord, $\\psi(\\varepsilon)= e$, l'arbre vide. Pour tout mot $w\\in\\mathcal F\\setminus\\{\\varepsilon\\}$, $w=uv$ où $u=+t-$ est irréductible, et $t$ est bien formé. Soient $t_1=\\psi(t)$ et $t_2=\\psi(v)$. On pose alors $\\psi(w) =(t_1, t_2)$.\n",
    "\n",
    "On vérifie aisément que pour tout entier $n$, $\\psi:\\mathcal F_n\\to\\mathcal T_n$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def well_formed_word_to_binary_tree(w):\n",
    "    if len(w) == 0: return empty_tree\n",
    "    else:\n",
    "        u, v = cut(w)\n",
    "        t1 = well_formed_word_to_binary_tree(u[1:-1])\n",
    "        t2 = well_formed_word_to_binary_tree(v)\n",
    "        return node(t1, t2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "well_formed_word_to_binary_tree('++--+-+-')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "La réciproque $\\chi:\\mathcal T\\to\\mathcal F$ de la fonction $\\psi$ est la suivante. $\\chi(e)=\\varepsilon$. Et pour tout $t\\in\\mathcal T$, $t=(t_1, t_2)$ où $t_1$ et $t_2$ sont des arbres binaires. On pose alors $\\chi(t)=+\\chi(t_1)-\\chi(t_2)$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def binary_tree_to_well_formed_word(t):\n",
    "    if t == empty_tree: return ''\n",
    "    else:\n",
    "        w1 = binary_tree_to_well_formed_word(left(t))\n",
    "        w2 = binary_tree_to_well_formed_word(right(t))\n",
    "        return '+' + w1 + '-' + w2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "w = random_well_formed_word(40)\n",
    "w1 = binary_tree_to_well_formed_word(well_formed_word_to_binary_tree(w))\n",
    "print(w)\n",
    "print(w1)\n",
    "print(w1 == w)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.2 Arbre binaire aléatoire"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Il est maintenant évident de créer un arbre binaire aléatoire."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def random_binary_tree(n):\n",
    "    w = random_well_formed_word(n)\n",
    "    return well_formed_word_to_binary_tree(w)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(random_binary_tree(100))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.3 Hauteur moyenne"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "La fonction ci-dessous renvoie la hauteur de l'arbre $t$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def hauteur(t):\n",
    "    if t == empty_tree: return 0\n",
    "    else:\n",
    "        h1 = hauteur(left(t))\n",
    "        h2 = hauteur(right(t))\n",
    "        return 1 + max([h1, h2])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "hauteur(random_binary_tree(100))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "La théorie prévoit que la hauteur moyenne d'un arbre binaire à $n$ noeuds est équivalente à $2\\sqrt{\\pi n}$ lorsque $n$ tend vers l'infini. L'écart-type de cette même hauteur étant équivalent à $2\\sqrt{\\pi(\\frac \\pi 3-1)n}$ (__source peu sûre, à vérifier !__), donc du même ordre de grandeur que la moyenne. Les tests numériques risquent donc de renvoyer des résulats pas très convaincants."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def average_height(n):\n",
    "    return 2 * sqrt(pi * n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "average_height(100)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "La fonction `stats_hauteur` prend deux entiers $n$ et $m$ en paramètres. Elle tire au sort $m$ arbres aléatoires à $n$ noeuds et renvoie la moyenne de leurs hauteurs."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def stats_hauteur(n, m):\n",
    "    s = 0\n",
    "    for k in range(m):\n",
    "        s = s + hauteur(random_binary_tree(n))\n",
    "    return s / m"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "stats_hauteur(100, 1000)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "L'ordre de grandeur est bon, sans plus. Il est possible (à vérifier) qu'un petit nombre d'arbres participent de façon significative à l'augmentation de l'espérance de la hauteur."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.4 Nombre moyen de feuilles"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Le nombre moyen de feuilles d'un arbre binaire à $n$ noeuds est $\\frac {n(n+1)} {2(2n-1)}\\sim \\frac n 4$. Je n'ai pas d'informations sur l'écart-type ..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def nombre_moyen_feuilles(n):\n",
    "    return n * (n + 1) / (2 * (2 * n - 1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "nombre_moyen_feuilles(100)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def nombre_feuilles(t):\n",
    "    if t == empty_tree: return 0\n",
    "    else:\n",
    "        t1, t2 = left(t), right(t)\n",
    "        if t1 == empty_tree and t2 == empty_tree: return 1\n",
    "        else:\n",
    "            f1 = nombre_feuilles(t1)\n",
    "            f2 = nombre_feuilles(t2)\n",
    "            return f1 + f2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "nombre_feuilles(random_binary_tree(100))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def stats_feuilles(n, m):\n",
    "    s = 0\n",
    "    for k in range(m):\n",
    "        s = s + nombre_feuilles(random_binary_tree(n))\n",
    "    return s / m"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "stats_feuilles(100, 1000)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Pas mal."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 3. Dessiner un arbre binaire"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "À quoi __ressemble__ un arbre binaire aléatoire \"moyen\" ? La réponse est un peu déroutante ...\n",
    "\n",
    "La fonction `draw_tree` ci-dessous dessine un arbre binaire. Elle est lente, la raison en est le choix de `matplotlib` pour le tracé. Mieux vaut ne pas tenter de dessiner des arbres ayant plus de quelques centaines de noeuds."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def draw_tree_aux(t, rect, dy):\n",
    "    if t == empty_tree: return\n",
    "    x1, x2, y1, y2 = rect\n",
    "    xm = (x1 + x2) // 2\n",
    "    t1, t2 = left(t), right(t)\n",
    "    draw_tree_aux(t1, (x1, xm, y1, y2 - dy), dy)\n",
    "    draw_tree_aux(t2, (xm, x2, y1, y2 - dy), dy)\n",
    "    if not t1 == empty_tree:\n",
    "        a, b = ((xm, (x1 + xm) // 2), (y2, y2 - dy))\n",
    "        plt.plot(a, b, 'k', marker='o')\n",
    "    if not t2 == empty_tree:\n",
    "        c, d = ((xm, (x2 + xm) // 2), (y2, y2 - dy))\n",
    "        plt.plot(c, d, 'k', marker='o')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def draw_tree(t):\n",
    "    d = 512\n",
    "    pad = 20\n",
    "    dy = (d - 2 * pad) / (hauteur(t))\n",
    "    draw_tree_aux(t, (pad, d - pad, pad, d - pad), dy)\n",
    "    plt.axis([0, d, 0, d])\n",
    "    plt.axis('off')\n",
    "    plt.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "N = 50\n",
    "t = random_binary_tree(N)\n",
    "draw_tree(t)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Les arbres dessinés apparaissent TRÈS déséquilibrés. Soit c'est normal, soit je dois refaire tous mes calculs, ce qui n'est pas concevable. Tentons juste une petite estimation. Soit $t$ un arbre binaire aléatoire à $n$ noeuds. Quelle est la probabilité que $t$ ait un seul fils ? Notons $\\mathcal T_{l,n}$ et $\\mathcal T_{r,n}$ les ensembles formés des arbres ayant respectivement seulement un fils gauche et seulement un fils droit.\n",
    "\n",
    "Notons $C_n=|\\mathcal T_n|$ le cardinal de $\\mathcal T_n$. $C_n$ est le $n$-ième __nombre de Catalan__, il vaut\n",
    "$$C_n=\\frac 1 {n+1}\\binom{2n}n$$\n",
    "\n",
    "De là $|\\mathcal T_{ln}|=C_{n-1}$ : un arbre à $n$ noeuds ayant seulement un fils gauche est formé d'une racine et d'un unique fils gauche ayant $n-1$ noeuds. La probabilité qu'un arbre soit dans $|\\mathcal T_{ln}|$ est donc (probabilité uniforme !) $\\frac{C_{n-1}}{C_n}=\\frac {n+1}{n}\\frac{\\binom{2n-2}{n-1}}{\\binom{2n} n}=\\frac{n+1}{2(2n-1)}$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Il en est évidemment de même pour $\\mathcal T_{rn}$. Or, pour $n\\ge 2$, les ensembles $\\mathcal T_{ln}$ et $\\mathcal T_{rn}$ sont disjoints (un arbre ne peut pas avoir ses deux fils vides s'il a au moins deux noeuds). Donc, $P(\\mathcal T_{rn}\\cup \\mathcal T_{rn}) = P(\\mathcal T_{ln})+P(\\mathcal T_{rn})=\\frac{n+1}{2n-1}\\sim \\frac 1 2$.\n",
    "\n",
    "La probabilité qu'un arbre ait un seul fils est asymptotiquement $\\frac 1 2$. Il y a une chance sur deux que l'arbre ait l'air penché :-)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}