{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Arbres binaires de recherche\n",
    "\n",
    "Marc Lorenzi\n",
    "\n",
    "8 juillet 2019"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import matplotlib.pyplot as plt\n",
    "import random"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "plt.rcParams['figure.figsize'] = (20, 6)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Ce notebook reprend dans les sections 1 et 2 un certain nombre de notions déjà vues dans le notebook sur les arbres, qu'il est conseillé d'avoir lu auparavant. Nous allons aborder le sujet des __arbres équilibrés__, et étudier une implémentation de l'arbre binaire de recherche appelée __arbre AVL__."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 1. Arbres binaires"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.1 Représentation des arbres en Python"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Un arbre binaire est soit vide, soit non vide. S'il n'est pas vide il possède une __racine__ et deux __fils__, un fils gauche et un fils droit, qui sont eux-mêmes des arbres binaires.\n",
    "\n",
    "Nous représenterons les arbres en Python comme suit :\n",
    "\n",
    "- L'arbre vide est représenté par `None`.\n",
    "- Si $t$ est un arbre non vide, de racine $x$, de fils gauche $u$ et de fils droit $v$, nous représenterons $t$ par le triplet $(x, u, v)$.\n",
    "\n",
    "Les fonctions ci-dessous résument tout. Elles permettent de récupérer les \"parties\" d'un arbre, de fabriquer un arbre à partir de ses parties, etc. Elles s'exécutent en temps $O(1)$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def vide(): return None\n",
    "def racine(t): return t[0]\n",
    "def fg(t): return t[1]\n",
    "def fd(t): return t[2]\n",
    "def arbre(x, u, v): return (x, u, v)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def est_vide(t): return t == None"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Notation__ : Nous utiliserons les notations suivantes : \n",
    "\n",
    "- L'arbre vide est noté $\\emptyset$.\n",
    "- Si $t$ est un arbre non vide de racine $x$, de fils gauche $u$ et de fils droit $v$, nous noterons $t=u\\oplus^x v$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Nous utiliserons de temps en temps pour nos explications l'exemple ci-dessous."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "exemple = (2, (1, (0, None, None), None), (5, (4, (3, None, None), None), \n",
    "          (12, (9, (8, (6, None, (7, None, None)), None), (10, None, (11, None, None))), \n",
    "          (13, None, (14, None, (18, (17, (15, None, (16, None, None)), None), (19, None, None)))))))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(exemple)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.2 Hauteur, nombre de noeuds"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "On définit inductivement la hauteur d'un arbre comme suit :\n",
    "\n",
    "__Définition__ :\n",
    "\n",
    "- $h(\\emptyset)=0$.\n",
    "- $h(u\\oplus^x v)=1+\\max(h(u), h(v))$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def hauteur(t):\n",
    "    if est_vide(t): return 0\n",
    "    else:\n",
    "        u, v = fg(t), fd(t)\n",
    "        return 1 + max(hauteur(u), hauteur(v))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "hauteur(exemple)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "On définit inductivement le nombre de noeuds d'un arbre comme suit :\n",
    "\n",
    "__Définition__ : \n",
    "\n",
    "- $|\\emptyset|=0$.\n",
    "- $|u\\oplus^x v|=1+|u|+|v|$.\n",
    "\n",
    "Remarquez la notation $|t|$ pour le nombre de noeuds de l'arbre $t$. La quantité $|t|$ est une mesure assez représentative de la __taille__ de l'arbre, c'est à dire de la mémoire qu'il occupe dans notre machine."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def nombre_noeuds(t):\n",
    "    if est_vide(t): return 0\n",
    "    else:\n",
    "        u, v = fg(t), fd(t)\n",
    "        return 1 + nombre_noeuds(u) + nombre_noeuds(v)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "nombre_noeuds(exemple)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.3 Dessiner un arbre"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Je n'entre pas dans les détails des fonctions ci-dessous. La fonction `dessiner` permet d'avoir une représentation graphique d'un arbre."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def dessiner_aux(t, rect, dy, labels, avl=False):\n",
    "    if est_vide(t): return\n",
    "    x1, x2, y1, y2 = rect\n",
    "    xm = (x1 + x2) // 2\n",
    "    x, t1, t2 = t\n",
    "    dessiner_aux(t1, (x1, xm, y1, y2 - dy), dy, labels, avl)\n",
    "    dessiner_aux(t2, (xm, x2, y1, y2 - dy), dy, labels, avl)\n",
    "    if labels: \n",
    "        if avl: plt.text(xm + 2, y2, str(x[0]), fontsize=12, horizontalalignment='left',verticalalignment='bottom')\n",
    "        else: plt.text(xm + 2, y2, str(x), fontsize=12, horizontalalignment='left',verticalalignment='bottom')\n",
    "    if not est_vide(t1):\n",
    "        a, b = ((xm, (x1 + xm) // 2), (y2, y2 - dy))\n",
    "        plt.plot(a, b, 'k', marker='o', markerfacecolor='r', markersize=8)\n",
    "    if not est_vide(t2):\n",
    "        c, d = ((xm, (x2 + xm) // 2), (y2, y2 - dy))\n",
    "        plt.plot(c, d, 'k', marker='o', markerfacecolor='r', markersize=8)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def dessiner(t, labels=True, avl=False):\n",
    "    d = 512\n",
    "    pad = 20\n",
    "    dy = (d - 2 * pad) / (hauteur(t))\n",
    "    dessiner_aux(t, (pad, d - pad, pad, d - pad), dy, labels, avl)\n",
    "    plt.axis([0, d, 0, d])\n",
    "    plt.axis('off')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "dessiner(exemple)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2. Arbres binaires de recherche"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.1 C'est quoi ?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Supposons que les noeuds de nos arbres appartiennent à un ensemble totalement ordonné. Nous allons nous intéresser à des arbres binaires dans lesquels il est entre-autres facile de retrouver un noeud. On les appelle les __arbres binaires de recherche__ (en abrégé : ABR). \n",
    "\n",
    "__Définition__ : Soit $t$ un arbre binaire.\n",
    "\n",
    "- Si $t$ est vide, c'est un ABR.\n",
    "- Si $t=u\\oplus^x v$, $t$ est un ABR lorsque\n",
    "\n",
    "    - $u$ est un ABR\n",
    "    - $v$ est un ABR\n",
    "    - Les noeuds de $u$ sont strictement inférieurs à $x$\n",
    "    - Les noeuds de $v$ sont supérieurs ou égaux à $x$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.2 Rechercher un objet dans un ABR"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Il est facile de rechercher un objet dans un ABR. Si l'objet est plus petit que la racine, on recherche dans le fils gauche. Sinon ... je vous laisse deviner."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def rechercher(x, t):\n",
    "    if est_vide(t): return False\n",
    "    else:\n",
    "        y, u, v = racine(t), fg(t), fd(t)\n",
    "        if x < y: return rechercher(x, u)\n",
    "        elif x > y: return rechercher(x, v)\n",
    "        else: return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "rechercher(18, exemple)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "rechercher(27, exemple)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "On voit facilement que le nombre de comparaisons à effectuer pour savoir si, oui ou non, un objet est dans l'arbre, est un $O(h)$ où $h$ est la hauteur de l'arbre. Si l'arbre est \"équilibré\" (en un sens à préciser, et c'est le but de ce notebook) on peut montrer que sa hauteur est logarithmique en le nombre de noeuds. La recherche est donc très efficace. Même pour des arbres ayant des millions de noeuds, ce sera presque instantané.\n",
    "\n",
    "En revanche, si l'arbre n'est pas équilibré on peut avoir un temps de recherche en $O(n)$ où $n$ est le nombre de noeuds de l'arbre. Dans ce cas on n'est pas contents du tout. Il existe des algorithmes permettant d'équilibrer les arbres, nous verrons cela un peu plus loin. Ci-dessous, un arbre où la fonction de recherche a un mauvais comportement."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def arbre_pas_equilibre_du_tout(n):\n",
    "    if n == 0: return vide()\n",
    "    else:\n",
    "        t = arbre_pas_equilibre_du_tout(n - 1)\n",
    "        return arbre(n, t, vide())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "dessiner(arbre_pas_equilibre_du_tout(10))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.3 Insérer un objet dans un ABR "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Insérer n'est pas plus difficile que rechercher :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def inserer(x, t):\n",
    "    if est_vide(t): return (x, vide(), vide())\n",
    "    else:\n",
    "        y, u, v = racine(t), fg(t), fd(t)\n",
    "        if x <= y: return (y, inserer(x, u), v)\n",
    "        else: return (y, u, inserer(x, v))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "La complexité de l'insertion en termes de comparaisons est la même que celle de la recherche : $O(h)$ où $h$ est la hauteur de l'arbre."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.4 ABR aléatoire"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Nous voici prêts à créer de façon automatique des arbres un peu plus gros que notre petit `exemple`. Voici tout d'abord une fonction `random_list`qui prend en paramètre un entier $n$ et renvoie une permutation des entiers de 0 à $n-1$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def random_list(n):\n",
    "    s = list(range(n))\n",
    "    random.shuffle(s)\n",
    "    return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "random_list(10)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Pour créer un ABR \"aléatoire\", on crée une liste aléatoire et on insère ses éléments dans un ABR initialement vide."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def random_abr(n):\n",
    "    s = random_list(n)\n",
    "    t = None\n",
    "    for x in s:\n",
    "        t = inserer(x, t)\n",
    "    return t"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "t = random_abr(100)\n",
    "dessiner(t)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Nous pouvons maintenant re-tester avec des arbres un peu plus conséquents les fonctions que nous avons déjà écrites."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "hauteur(random_abr(10000))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "nombre_noeuds(random_abr(10000))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Le résultat renvoyé par la fonction précédente est assez rassurant."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.5 Minimum, maximum, d'un ABR"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Le maximum d'un ABR est facile à trouver. On part de la racine et on va à droite, à droite, ... Bref c'est au fond à droite :)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def maximum(t):\n",
    "    if est_vide(t): raise Exception('Arbre Vide')\n",
    "    else:\n",
    "        x, v = racine(t), fd(t)\n",
    "        if est_vide(v): return x\n",
    "        else: return maximum(v)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "maximum(random_abr(1000))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def minimum(t):\n",
    "    if est_vide(t): raise Exception('Arbre Vide')\n",
    "    else:\n",
    "        x, u = racine(t), fg(t)\n",
    "        if est_vide(u): return x\n",
    "        else: return minimum(u)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "minimum(random_abr(1000))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.6 Un arbre est-il un ABR ?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "La fonction ci-dessous renvoie `True` si son paramètre est un ABR, et `False` sinon. Remarquez que pour savoir si tous les noeuds de $t_1$ sont inférieurs à $x$, il suffit de regarder si c'est le cas pour le maximum de $t_1$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def est_ABR(t):\n",
    "    if est_vide(t): return True\n",
    "    else:\n",
    "        x, u, v = racine(t), fg(t), fd(t)\n",
    "        b = est_ABR(u) and est_ABR(v)\n",
    "        if est_vide(u): b1 = True\n",
    "        else: b1 = maximum(u) < x\n",
    "        if est_vide(v): b2 = True\n",
    "        else: b2 = minimum(v) >= x\n",
    "        return b and b1 and b2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "est_ABR(random_abr(1000))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Remarque__ : Le fait que nous obtenions `True` à la question \"Un ABR aléatoire est-il un ABR ?\" nous incite à penser que les fonctions `minimum`, `maximum`, `inserer`, etc. sont correctes. Ou alors que tout est faux et que nous avons énormément de chance :-). "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.7 Supprimer un noeud dans un ABR"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "On fait dans ce paragraphe l'hypothèse que nos ABR ont tous leurs noeuds distincts. Soit $t$ un ABR. Soit $x$ un noeud de $t$ qui a un fils droit non vide. Alors $x$ n'est pas le maximum de $t$ (cf plus haut) et possède donc un __successeur__ dans l'arbre, c'est à dire un noeud $s$ tel que $x<s$ mais pour tout noeud $y$ de l'arbre, $y \\le x$ ou $s\\le y$. Dit autrement, il n'y a aucun noeud de l'arbre strictement compris entre $x$ et $s$. Soit $m$ le minimum du fils droit de $x$ : montrons que $m$ est le successeur de $x$.\n",
    "\n",
    "Pour cela, soit $y$ un noeud de l'arbre différent de $x$ et appelons $z$ le plus proche ancêtre commun de $x$ et $y$. Pour que cela soit bien clair, reprenons notre exemple."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "dessiner(exemple)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Par exemple, le plus proche ancêtre commun de 10 et 15 est 12. Un certain nombre  de cas se présentent :"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Cas 1__ : $z=x$ et $y$ est dans le fils droit de $x$. Alors $m \\le y$ par définition de $m$, minimum du fils droit.\n",
    "\n",
    "__Cas 2__ : $z=x$ et $y$ est dans le fils gauche de $x$. Alors $y \\le x$ puisque $t$ est un ABR.\n",
    "\n",
    "__Cas 3__ : $x$ est dans le fils gauche de $z$ et $y$ est dans le fils droit de $z$. Alors $m\\le y$ par définition de $m$.\n",
    "\n",
    "__Cas 4__ : $y$ est dans le fils gauche de $z$ et $x$ est dans le fils droit de $z$. Alors $y\\le z$ et $z< x$ puisque $t$ est un ABR. Donc $y<x$.\n",
    "\n",
    "Le successeur de $x$ est donc bien $m$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "La fonction de suppression s'en déduit. On désire supprimer $x$ dans l'ABR $t$. Que peut-il arriver ? Si $x$ n'est pas la racine de $t$, on supprime $x$ dans le fils gauche ou le fils droit de $t$. Sinon :\n",
    "\n",
    "- si $x$ n'a pas de fil droit, c'est facile, renvoyer le fils gauche de $t$.\n",
    "- Si $x$ a un fils droit, soit $m$ le minimum de ce fils droit. Remplacer $x$ par $m$ et supprimer récursivement $m$ du fils droit de $x$.\n",
    "\n",
    "On vérifie facilement que l'on conserve la structure d'ABR parce que aucun noeud de $t$ n'est compris entre $x$ et $m$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def supprimer(x, t):\n",
    "    if est_vide(t): return None\n",
    "    else:\n",
    "        y, u, v = racine(t), fg(t), fd(t)\n",
    "        if x < y: return (y, supprimer(x, u), v)\n",
    "        elif x > y: return (y, u, supprimer(x, v))\n",
    "        elif est_vide(v): return u\n",
    "        else:\n",
    "            m = minimum(v)\n",
    "            return (m, u, supprimer(m, v))            "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Testons. Partant d'un ABR aléatoire à 16 noeuds, on supprime successivement les noeuds de valeurs 0 à 14. À la fin il ne doit en rester qu'un :-). Le tableau de graphique se lit de gauche à droite, puis du haut vers le bas."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "t = random_abr(16)\n",
    "ts = [t]\n",
    "for k in range(15):\n",
    "    t = supprimer(k, t)\n",
    "    ts.append(t)\n",
    "for k in range(1, 17):\n",
    "    plt.subplot(4, 4, k)\n",
    "    dessiner(ts[k - 1])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Remarque__ : Soit $t$ un ABR. Soit $x$ un noeud de $t$ qui n'a pas de fils droit et qui n'est pas le maximum de $t$. Où est le successeur de $x$ ? Eh bien le successeur de $x$ est le plus proche ancêtre de $x$ dont la racine du fils gauche est aussi un ancêtre de $x$. Démonstration laissée au lecteur.\n",
    "\n",
    "Sur notre exemple :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "dessiner(exemple)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Les ancêtres de 11 (au sens large) sont : 11, 10, 9, 12, 5 et 2. Le successeur de 11 est 12 parce que la racine du fils gauche de 12 est 9, qui est encore un ancêtre de 11. Et 12 est le plus proche ancêtre de 11 à vérifier cette propriété.\n",
    "\n",
    "Dit autrement, on part de 11, on monte à gauche, puis à gauche, etc. Au premier virage à droite on est arrivés. Bref, c'est la première à droite en montant."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 3. Arbres équilibrés"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Venons-en au fait."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3.1 Comparaison entre hauteur et nombre de noeuds"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Proposition__ : Soit $t$ un arbre binaire. On a\n",
    "\n",
    "$$h(t)\\le |t|\\le 2^{h(t)}-1$$\n",
    "\n",
    "__Démonstration__ : Faisons une récurrence sur la hauteur $h$ de l'arbre $t$.\n",
    "\n",
    "- Si $h=0$, alors $t=\\emptyset$ et $|t|=0$. La double inégalité à montrer est alors une double égalité.\n",
    "\n",
    "- Soit $h\\in\\mathbb N$. Supposons la propriété vraie pour tous les arbres de hauteur inférieure ou égale à $h$. Soit $t=u\\oplus^x v$ un arbre de hauteur $h+1$. On a, par exemple, $h(u)\\le h(v)= h$. De plus, \n",
    "\n",
    "$$|t|=|u|+|v|+1$$\n",
    "\n",
    "Pour la première inégalité, on a\n",
    "\n",
    "$$h(t)=h(v)+1\\le |v|+1\\le |u|+|v|+1=|t|$$\n",
    "\n",
    "Pour la deuxième inégalité,\n",
    "\n",
    "$$|t|=|u|+|v|+1\\le (2^{h(u)}-1)+(2^{h(v)}-1)+1\\le 2(2^h-1)+1=2^{h+1}-1$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "De la proposition précédente on déduit, en passant aux logarithmes en base 2, que\n",
    "\n",
    "$$h(t)\\ge \\lg(|t|+1)$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Nous avons vu dans la partie 1 que les opérations d'insertion et de suppression dans un ABR $t$ s'effectuaient en $O(h(t))$. Ce temps est donc au moins logarithmique en le nombre de noeuds de $t$ ... dit autrement nous venons d'obtenir exactement le contraire de ce que nous aurions voulu, un temps __au plus__ logarithmique en $|t|$ !\n",
    "\n",
    "Remarquons que le majorant $h(t)\\le |t|$  est terrible. Il semble suggérer que pour certains ABR, l'insertion d'un élément se fait en temps __linéaire__ en le nombre de noeuds de $t$. Si c'est le cas, les ABR ne servent à rien. Autant se servir de listes pour stocker nos données.\n",
    "\n",
    "Alors, que faire ?\n",
    "\n",
    "- Tout d'abord, trouver une condition simple sur l'arbre $t$ pour que sa hauteur soit logarithmique en son nombre de noeuds.\n",
    "- Puis imaginer une amélioration des algorithmes que nous avons vus sur les ABR pour que cette condition soit préservée par insertion ou suppression d'un noeud."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3.2 C'est quoi un arbre équilibré ?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Définition__ : Nous donnons une définition inductive de la notion d'arbre équilibré.\n",
    "\n",
    "- $\\emptyset$ est équilibré.\n",
    "- L'arbre $u\\oplus^x v$ est équilibré lorsque\n",
    "\n",
    "    - $u$ est équilibré\n",
    "    - $v$ est équilibré\n",
    "    - $|h(u)-h(v)|\\le 1$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def est_equilibre(t):\n",
    "    if est_vide(t): return True\n",
    "    else:\n",
    "        u, v = fg(t), fd(t)\n",
    "        return est_equilibre(u) and est_equilibre(v) and abs(hauteur(u) - hauteur(v)) <= 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "est_equilibre(exemple)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "On s'en serait doutés :-)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Proposition__ : Il existe un réel $c>1$ tel que, pour tout arbre équilibré $t$, on ait\n",
    "\n",
    "$$|t|\\ge c^{h(t)}-1$$\n",
    "\n",
    "et donc\n",
    "\n",
    "$$h(t)\\le \\log_c(1+|t|)$$\n",
    "\n",
    "__Démonstration__ : Une récurrence sur la hauteur s'impose. Pour l'arbre vide, n'importe quel réel $c>1$ fait l'affaire. Soit $h\\in\\mathbb N$. Supposons trouvé un réel $c>1$ convenant pour tous les arbres équilibrés de hauteur inférieure ou égale à $h$. Soit $t=u\\oplus^x v$ un arbre équilibré de hauteur $h+1$. On a, par exemple,\n",
    "\n",
    "$$h-1\\le h(u)\\le h(v)= h$$\n",
    "\n",
    "De là,\n",
    "\n",
    "$$|t|=|u|+|v|+1\\ge (c^{h-1}-1)+(c^h-1)+1=c^{h+1}\\left(\\frac 1 {c^2} + \\frac 1 c\\right) - 1$$\n",
    "\n",
    "Existe-t-il un réel $c>1$ tel que $\\frac 1 {c^2}+\\frac 1 c=1$ ? Ce serait le nombre idéal pour nous. Un tel réel vérifierait\n",
    "\n",
    "$$c^2=c+1$$\n",
    "\n",
    "Mais oui, un tel réel existe ! Il s'agit du nombre d'or, $c=\\frac 1 2(1 +\\sqrt 5)$. Notre proposition est donc montrée en prenant pour $c$ le nombre d'or. Nous le noterons dorénavant $\\phi$. \n",
    "\n",
    "__En résumé__ : On a pour tout arbre $t$ équilibré,\n",
    "\n",
    "$$\\log_2(1+|t|)\\le h(t)\\le \\log_\\phi(1+|t|)$$\n",
    "\n",
    "La hauteur d'un arbre équilibré est donc logarithmique en son nombre de noeuds."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.3 Arbres de Fibonacci."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Quand le nombre d'or apparaît, Fibonacci n'est jamais bien loin ... Dans les arbres que nous allons examiner la valeur des noeuds ne nous intéresse pas. Mettons par exemple les noeuds à 0.\n",
    "\n",
    "__Définition__ : La suite de Fibonacci est la suite d'arbres binaires définie par\n",
    "\n",
    "- $F_0$ est l'arbre vide.\n",
    "- $F_1$ a une racine et pas de fils.\n",
    "- Pour tout $n\\in\\mathbb N, F_{n+2}=F_{n}\\oplus^0 F_{n+1}$\n",
    "\n",
    "où la valeur de la racine, sans importance, n'est pas précisée."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def fibonacci(n):\n",
    "    f = vide()\n",
    "    g = arbre(0, vide(), vide())\n",
    "    for k in range(n):\n",
    "        f, g = g, arbre(0, f, g)\n",
    "    return f"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "dessiner(fibonacci(10), labels=False)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Quelle est la hauteur d'un arbre de Fibonacci ?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "[hauteur(fibonacci(k)) for k in range(10)]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Proposition__ : Pour tout $n\\in\\mathbb N$, $h(F_n)=n$.\n",
    "\n",
    "__Démonstration__ : Récurrence facile à deux termes sur $n$, laissée au lecteur."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Combien de noeuds un arbre de Fibonacci possède-t-il ? "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "[nombre_noeuds(fibonacci(k)) for k in range(10)]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Définissons la suite $(f_n)_{n\\ge 0}$ des __nombres de Fibonacci__ par\n",
    "\n",
    "- $f_0=0$\n",
    "- $f_1=1$\n",
    "- Pour tout $n\\in\\mathbb N$, $f_{n+2}=f_n+f_{n+1}$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def nb_fibo(n):\n",
    "    a = 0\n",
    "    b = 1\n",
    "    for k in range(n):\n",
    "        a, b = b, a + b\n",
    "    return a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print([nb_fibo(k) for k in range(10)])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print([nb_fibo(k + 2) - 1 for k in range(10)])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Proposition__ : On a pour tout $n\\in\\mathbb N$,\n",
    "\n",
    "$$|F_n| = f_{n+2}-1$$\n",
    "\n",
    "__Démonstration__ : On fait une récurrence à deux termes sur $n$.\n",
    "\n",
    "- Pour $n=0,1$ c'est évident.\n",
    "- Soit $n\\in\\mathbb N$. Supposons la propriété vraie pour $n$ et $n+1$. On a alors\n",
    "\n",
    "$$|F_{n+2}|=|F_n\\oplus F_{n+1}|=|F_n| + |F_{n+1}|+1=f_{n+2}-1+f_{n+3}-1+1=f_{n+4}-1$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Remarquons maintenant que \n",
    "\n",
    "$$f_n=\\frac{\\phi^n-{\\hat \\phi}^n}{\\phi-\\hat \\phi}$$\n",
    "\n",
    "où $\\phi$, rappelons-le, est le nombre d'or et $\\hat \\phi=\\frac 1 2 (1-\\sqrt 5)$. On a clairement $f_n\\sim \\frac 1 {\\phi-\\hat \\phi} \\phi^n$. De là,\n",
    "\n",
    "$$\\log_c(|F_n|+1)=\\log_\\phi f_{n+2}\\sim n +2\\sim n = h(F_n)$$\n",
    "\n",
    "Ceci montre que l'inégalité que nous avons montrée dans la section précédente est __asymptotiquement optimale__ : les arbres de Fibonacci sont, d'une certaine manière, les plus déséquilibrés des arbres équilibrés :-)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "dessiner(fibonacci(13), labels=False)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 3. Arbres AVL"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Les arbres AVL tirent leur nom des initiales de leurs inventeurs (découvreurs ?), Georgii Adelson-Velsky and Evgenii Landis. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3.1 C'est quoi ?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Le problème des ABR tels que nous les avons définis est que des insertions ou des suppressions peuvent déséquilibrer l'arbre. Or, le coût de ces opérations est fortement lié au fait que l'arbre soit équilibré. Petit exemple :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "t = vide()\n",
    "for k in range(10): t = inserer(k, t)\n",
    "dessiner(t)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "On voit facilement que le coût de $n$ insertions d'entiers successifs dans un arbre initialement vide est $O(n^2)$, ce qui n'est pas acceptable. Alors, impasse ? Pas forcément, il s'agit de réfléchir à la façon de maintenir les arbres équilibrés lors d'une insertion ou d'une suppression. \n",
    "\n",
    "Il existe différentes approches du problème : arbres 2-3-4, arbres rouges et noirs, arbres AVL, ... Nous allons nous concentrer sur les arbres AVL."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Dans un arbre AVL, on stocke à la racine le couple formé de la \"vraie\" valeur de la racine et de la hauteur de l'arbre. Le calcul de la hauteur d'un arbre AVL se fait donc en $O(1)$ puisqu'il suffit de savoir lire :-)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def racine_avl(t): \n",
    "    if est_vide(t):\n",
    "        raise Exception('Arbre vide')\n",
    "    else: return t[0][0]\n",
    "\n",
    "def hauteur_avl(t):\n",
    "    if est_vide(t): return 0\n",
    "    else: return t[0][1]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Il est alors facile de fabriquer en temps $O(1)$ un arbre AVL de racine $x$ et de fils $u$ et $v$ :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def arbre_avl(x, u, v):\n",
    "    h = 1 + max(hauteur_avl(u), hauteur_avl(v))\n",
    "    return ((x, h), u, v)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Il faut également réécrire les fonctions calculant le minimum et le maximum d'un arbre AVL."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def maximum_avl(t):\n",
    "    if est_vide(t): raise Exception('Arbre Vide')\n",
    "    else:\n",
    "        x, v = racine_avl(t), fd(t) \n",
    "        if est_vide(v): return x\n",
    "        else: return maximum_avl(v)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def minimum_avl(t):\n",
    "    if est_vide(t): raise Exception('Arbre Vide')\n",
    "    else:\n",
    "        x, u = racine_avl(t), fg(t)\n",
    "        if est_vide(u): return x\n",
    "        else: return minimum_avl(u)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3.2 Rotations !"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Définissons deux fonctions de l'ensemble des arbres binaires sur lui-même, la rotation droite $\\rho_d$ et la rotation gauche $\\rho_g$. Pour tous arbres $u,v,w$ :\n",
    "\n",
    "- $\\rho_d((u\\oplus^x v)\\oplus^y w)= u\\oplus^x(v\\oplus^y w)$.\n",
    "- $\\rho_g(u\\oplus^x(v\\oplus^y w)) = (u\\oplus^x v)\\oplus^y w$.\n",
    "\n",
    "L'arbre $\\rho_d(t)$ est défini pour tout arbre $t$ non vide dont le fils gauche est lui-même non vide. Propriété analogue pour $\\rho_g$.\n",
    "\n",
    "__Exercice essentiel__ : Dessinez un arbre et sa rotation droite. Pourquoi appelle-t-on cela une rotation ?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def rotation_droite(t):\n",
    "    x = racine_avl(t)\n",
    "    t1, w = fg(t), fd(t)\n",
    "    u, v = fg(t1), fd(t1)\n",
    "    y = racine_avl(t1)\n",
    "    return arbre_avl(y, u, arbre_avl(x, v, w)) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def rotation_gauche(t):\n",
    "    x = racine_avl(t)\n",
    "    u, t2 = fg(t), fd(t)\n",
    "    v, w = fg(t2), fd(t2)\n",
    "    y = racine_avl(t2)\n",
    "    return arbre_avl(y, arbre_avl(x, u, v), w) "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Voici un petit exemple."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "t = arbre_avl(3, \n",
    "              arbre_avl(1,\n",
    "                        arbre_avl(0, vide(), vide()),\n",
    "                        arbre_avl(2, vide(), vide())), \n",
    "             arbre_avl(4, vide(), vide()))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "dessiner(t, avl=True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "t1 = rotation_droite(t) \n",
    "dessiner(t1, avl=True)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Bien entendu, une rotation gauche de $t_1$ fait revenir à l'arbre de départ. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "dessiner(rotation_gauche(t1), avl=True)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Propriété__ : Les opérations de rotation conservent la structure d'ABR.\n",
    "\n",
    "__Démonstration__ : En exercice. Il suffit d'utiliser la définition d'ABR."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Appelons __facteur d'équilibre__ d'un arbre le nombre suivant.\n",
    "\n",
    "- $\\epsilon(\\emptyset)=0$.\n",
    "\n",
    "- $\\epsilon(u\\oplus^x v)=h(u)-h(v)$.\n",
    "\n",
    "Le facteur d'équilibre d'un arbre équilibré est donc $-1$, 0 ou $1$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def facteq(t):\n",
    "    if est_vide(t): return 0\n",
    "    else:\n",
    "        return hauteur_avl(fg(t)) - hauteur_avl(fd(t))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Nous allons maintenant voir comment, à partir d'un arbre __légérement__ déséquilibré, on peut rétablir l'équilibre par des rotations.\n",
    "\n",
    "Soit $t=(u\\oplus^x v)\\oplus^y w$ un arbre. Supposons que $u\\oplus^x v$ et $w$ sont équilibrés, mais que $t$ est légérement déséquilibré, c'est à dire que son facteur d'équilibre vaut $-2$ ou 2. Comment rééquilibrer $t$ ? \n",
    "\n",
    "Discutons le cas où $\\epsilon(t)=2$. L'autre cas est identique, en échangeant rotations droites et rotations gauches. Soit $h$ la hauteur de $t$. On a donc \n",
    "\n",
    "$$h(u\\oplus^x v)=h-1$$ \n",
    "\n",
    "et \n",
    "\n",
    "$$h(w)=h-3$$\n",
    "\n",
    "Trois cas se présentent, selon la valeur du facteur d'équilibre de $u\\oplus^x v$.\n",
    "\n",
    "- Cas 1, $\\epsilon(u\\oplus^x v)=1$. On a donc $h(u)=h-2$ et $h(v)=h-3$. \n",
    "\n",
    "Faisons une rotation droite de $t$. Voici dans un tableau les hauteurs et facteurs d'équilibre qui nous intéressent.\n",
    "\n",
    "$$\\begin{array}{|c|c|c|c|c|c|}\n",
    "\\hline\n",
    "&u&v&w&v\\oplus^y w&u\\oplus^x (v\\oplus^y w)\\\\\n",
    "\\hline\n",
    "h&h-2&h-3&h-3&h-2&h-1\\\\\n",
    "\\hline\n",
    "\\epsilon&&&&0&0\\\\\n",
    "\\hline\n",
    "\\end{array}$$\n",
    "\n",
    "- Cas 2, $\\epsilon(u\\oplus^x v)=0$. On a donc $h(u)=h-2$ et $h(v)=h-2$. \n",
    "\n",
    "Ici encore, faisons une rotation droite de $t$.\n",
    "\n",
    "$$\\begin{array}{|c|c|c|c|c|c|}\n",
    "\\hline\n",
    "&u&v&w&v\\oplus^y w&u\\oplus^x (v\\oplus^y w)\\\\\n",
    "\\hline\n",
    "h&h-2&h-2&h-3&h-1&h\\\\\n",
    "\\hline\n",
    "\\epsilon&&&&1&-1\\\\\n",
    "\\hline\n",
    "\\end{array}$$\n",
    "\n",
    "- Cas 3, $\\epsilon(u\\oplus^x v)=-1$. On a donc $h(u)=h-3$ et $h(v)=h-2$. \n",
    "\n",
    "Là, nous allons faire deux rotations : une rotation gauche de $u\\oplus^x v$, suivie d'une rotation droite du \"nouveau\" $t$. Qu'est ce que cela donne ? Posons $v=v_1\\oplus^z v_2$. Nous avons\n",
    "\n",
    "$$\n",
    "\\begin{eqnarray*}\n",
    "\\rho_d(\\rho_g(u\\oplus^x(v_1\\oplus^z v_2))\\oplus^y w)&=&\\rho_d((u\\oplus^x v_1)\\oplus^z v_2)\\oplus^y w)\\\\\n",
    "&=&(u\\oplus^x v_1)\\oplus^z (v_2\\oplus^y w)\n",
    "\\end{eqnarray*}$$\n",
    "\n",
    "Comme $v_1\\oplus^z v_2$ est équilibré et de hauteur $h-2$, nous avons 3 possibilités pour les hauteurs de $v_1$ et $v_2$. Résumons tout cela dans un tableau.\n",
    "\n",
    "$$\\begin{array}{|c|c|c|c|c|c|c|c|}\n",
    "\\hline\n",
    "&u&v_1&v_2&w&u\\oplus^x v_1&v_2\\oplus^y w&(u\\oplus^x v_1)\\oplus^z (v_2\\oplus^y w)\\\\\n",
    "\\hline\n",
    "h_1&h-3&h-3&h-3&h-3&h-2&h-2&h-1\\\\\n",
    "\\hline\n",
    "\\epsilon_1&&&&&0&0&0\\\\\n",
    "\\hline\n",
    "h_2&h-3&h-2&h-3&h-3&h-2&h-2&h-1\\\\\n",
    "\\hline\n",
    "\\epsilon_2&&&&&1&0&0\\\\\n",
    "\\hline\n",
    "h_3&h-3&h-3&h-2&h-3&h-2&h-2&h-1\\\\\n",
    "\\hline\n",
    "\\epsilon_3&&&&&0&-1&0\\\\\n",
    "\\hline\n",
    "\\end{array}$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Dans tous les cas, on constate que les opérations de rotation effectuées donnent bien des arbres équilibrés. Remarquez également que la hauteur de l'arbre obtenu est la même que celle de l'arbre de départ, voire un de moins. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Voici donc la fonction `reequilibrer` qui prend en paramètres un objet $y$ et deux arbres équilibrés $u$ et $v$, et qui effectue un recollement équilibré."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def reequilibrer(y, u, v):\n",
    "    e = hauteur_avl(u) - hauteur_avl(v)\n",
    "    if abs(e) <= 1: return arbre_avl(y, u, v)\n",
    "    elif e == 2:\n",
    "        e1 = facteq(u)\n",
    "        if e1 == -1: u = rotation_gauche(u)\n",
    "        return rotation_droite(arbre_avl(y, u, v))\n",
    "    elif e == -2:\n",
    "        e2 = facteq(v)\n",
    "        if e2 == 1: v = rotation_droite(v)\n",
    "        return rotation_gauche(arbre_avl(y, u, v))\n",
    "    else: raise Exception('Cas impossible')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Remarque__ : Les fonctions de rotation et de rééquilibrage s'exécutent toutes en temps $O(1)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3.3 Insertion dans un arbre AVL"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Voici la fonction d'insertion dans un AVL."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def inserer_avl(x, t):\n",
    "    if est_vide(t):\n",
    "        return arbre_avl(x, vide(), vide())\n",
    "    else:\n",
    "        y = racine_avl(t)\n",
    "        if x < y:\n",
    "            return reequilibrer(y, inserer_avl(x, fg(t)), fd(t))\n",
    "        else:\n",
    "            return reequilibrer(y, fg(t), inserer_avl(x, fd(t)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Proposition__ : L'insertion dans un AVL équilibré $t$ renvoie un AVL équilibré $t'$ tel que $h(t)\\le h(t')\\le h(t)+1$.\n",
    "\n",
    "__Démonstration__ : Gardons la démonstration pour tout à l'heure. Nous avons hâte de tester notre nouvelle fonction !"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Rappelez-vous la catastrophe qui était survenue lors de l'insertion de $n$ entiers successifs dans un ABR. Maintenant, plus de souci !"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "t = vide()\n",
    "for k in range(100):\n",
    "    t = inserer_avl(k, t)\n",
    "dessiner(t, True, avl=True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def est_ABR_avl(t):\n",
    "    if est_vide(t): return True\n",
    "    else:\n",
    "        x, u, v = racine_avl(t), fg(t), fd(t)\n",
    "        b = est_ABR_avl(u) and est_ABR_avl(v)\n",
    "        if est_vide(u): b1 = True\n",
    "        else: b1 = maximum_avl(u) < x\n",
    "        if est_vide(v): b2 = True\n",
    "        else: b2 = minimum_avl(v) >= x\n",
    "        return b and b1 and b2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(est_ABR_avl(t))\n",
    "print(est_equilibre(t))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Et voici une fonction `random_avl` ..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def random_avl(n):\n",
    "    s = list(range(n))\n",
    "    random.shuffle(s)\n",
    "    t = vide()\n",
    "    for x in s: t = inserer_avl(x, t)\n",
    "    return t"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "t = random_avl(100)\n",
    "dessiner(t, avl=True)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Voici un \"gros\" arbre AVL."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "t = random_avl(1000)\n",
    "dessiner(t, False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(est_ABR_avl(t))\n",
    "print(est_equilibre(t))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Si vous vous inquiétez du temps mis pour afficher un arbre AVL aléatoire de 1000 noeuds, sachez que ce n'est pas la faute de `inserer` mais celle de `dessiner`. La preuve, voici le calcul quasi-instantané d'un arbre AVL aléatoire de $10^4$ noeuds. Je vous déconseille de le dessiner. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "t = random_avl(10000)\n",
    "print(nombre_noeuds(t))\n",
    "print(est_ABR_avl(t))\n",
    "print(est_equilibre(t))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Vous n'avez pas oublié qu'il nous reste une démonstration à faire ? Rappelons la propriété.\n",
    "\n",
    "__Propriété__ : L'insertion dans un AVL équilibré $t$ renvoie un AVL équilibré $t'$ tel que $h(t)\\le h(t')\\le h(t)+1$.\n",
    "\n",
    "__Démonstration__ : On fait une récurrence forte sur la hauteur de $t$.\n",
    "\n",
    "- C'est évident si $t$ est vide.\n",
    "- Soit $h\\in\\mathbb N$. Supposons la propriété vraie pour tous les arbres AVL équilibrés de hauteur inférieure ou égale à $h$. Soit $t=u\\oplus^y v$ un arbre AVL équilibré de hauteur $h+1$. Pour fixer les idées, $h(u)=h$ et $h(v)= h$ ou $h-1$. Insérons un objet $x$ dans $t$. Deux cas se présentent.\n",
    "\n",
    "- Cas 1, $x < y$. Par l'hypothèse de récurrence, l'insertion de $x$ dans $u$ produit un arbre AVL équilibré $u'$ de hauteur $h$ ou $h+1$. L'arbre $t'=u'\\oplus^y v$ a donc un facteur d'équilibre de 1, ou 2. Son rééquilibrage renvoie donc un arbre AVL équilibré. Le lecteur est invité à vérifier que le rééquilibrage produit un arbre  de hauteur $h+1$ ou $h+2$. Il faut pour cela considérer plusieurs cas, selon le facteur d'équilibre de $u'$.\n",
    "\n",
    "- Cas 2, $x >= y$. Par l'hypothèse de récurrence, l'insertion de $x$ dans $v$ produit un arbre AVL équilibré $v'$ de hauteur $h-1$ ou $h$. L'arbre $t'=u\\oplus^y v'$ a donc un facteur d'équilibre de 0 ou 1. Il est donc équilibré et son rééquilibrage le renvoie tel quel. De plus, la hauteur de $t'$ est $h+1$.\n",
    "\n",
    "La fonction d'insertion crée donc des arbres AVL équilibrés qui, comme nous l'avons déjà vu plus haut, ont aussi la propriété d'ABR."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3.4 Complexité de l'insertion"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Propriété__ : L'insertion d'un objet dans un arbre AVL équilibré $t$ a une complexité en $O(\\log |t|)$.\n",
    "\n",
    "__Démonstration__ : En effet, nous avons vu que l'insertion a une complexité en $O(h(t))$, et comme l'arbre est équilibré, $h(t)=O(\\log |t|)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3.5 Suppression dans un arbre AVL"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Je ne détaille pas. Cette fonction est quasiment analogue à la fonction de suppression dans les ABR. Il faut juste penser à rééquilibrer a bon escient. Cette fonction a, comme la fonction d'insertion, une complexité en $O(\\log |t|)$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def supprimer_avl(x, t):\n",
    "    if est_vide(t): return vide()\n",
    "    else:\n",
    "        y, u, v = racine_avl(t), fg(t), fd(t)\n",
    "        if x < y: return reequilibrer(y, supprimer_avl(x, u), v)\n",
    "        elif x > y: return reequilibrer(y, u, supprimer_avl(x, v))\n",
    "        elif est_vide(v): return u\n",
    "        else:\n",
    "            m = minimum_avl(v)\n",
    "            return reequilibrer(m, u, supprimer_avl(m, v))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Comme pour les ABR, voici une illustration de la fonction de suppression. Partant d'un arbre AVL aléatoire dont les noeuds sont les entiers de 0 à 19, on supprime successivement les noeuds de valeurs 0 à 18. À la fin il ne doit en rester qu'un :-)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "t = random_avl(20)\n",
    "ts = [t]\n",
    "for k in range(19):\n",
    "    t = supprimer_avl(k, t)\n",
    "    ts.append(t)\n",
    "for k in range(1, 21):\n",
    "    plt.subplot(5, 4, k)\n",
    "    dessiner(ts[k - 1], avl=True)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 4. Retour sur les ABR aléatoires"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 4.1 Nombre d'ABR à $n$ noeuds"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Soit $E$ un ensemble totalement ordonné de cardinal $n\\in\\mathbb E$. Combien y a-t-il d'ABR dont les noeuds sont distincts et sont exactement les éléments de $E$ ? Clairement, cela ne dépend que de $n$ et pas de l'ensemble particulier $E$. Notons donc $C_n$ le nombre recherché.\n",
    "\n",
    "- Si $n=0$, c'est facile, il n'y a qu'un ABR qui convient, c'est $\\emptyset$. On a donc $C_0=1$.\n",
    "- Supposons maintenant $n\\ge 1$. Notons $E=\\{x_0,\\ldots,x_{n-1}\\}$ où $x_0<\\ldots<x_{n-1}$. Pour $0\\le k\\le n-1$, combien y a-t-il d'ABR dont la racine est $x_k$ ? Pour un tel ABR, les noeuds de son fils gauche sont $x_0,\\ldots,x_{k-1}$, au nombre  de $k$. Il y a donc $C_k$ fils gauches possibles. De même, il y a $C_{n-1-k}$ fils droits possibles. Ainsi, il y a $C_kC_{n-1-k}$ ABR dont la racine est $x_k$. En conclusion,\n",
    "\n",
    "$$C_n=\\sum_{k=0}^{n-1}C_kC_{n-1-k}$$\n",
    "\n",
    "Cette relation de récurrence a l'air terrible mais on peut la résoudre. Posons\n",
    "\n",
    "$$f(z)=\\sum_{n=0}^\\infty C_nz^n$$\n",
    "\n",
    "Pour ne pas rallonger un notebook déjà terriblement long, j'admettrai ici que cette série entière a un rayon de convergence strictement positif (il vaut en fait $\\frac 1 4$). On a\n",
    "\n",
    "$$f(z)^2=\\sum_{n=0}^\\infty a_n z^n$$\n",
    "\n",
    "où $a_n=\\sum_{k=0}^{n}C_kC_{n-k}=C_{n+1}$. Ainsi,\n",
    "\n",
    "$$zf(z)^2=\\sum_{n=0}^\\infty C_{n+1} z^{n+1}=f(z)-1$$\n",
    "\n",
    "ou encore\n",
    "\n",
    "$$zf(z)^2-f(z)+1=0$$\n",
    "\n",
    "$f(z)$ est donc racine d'une équation du second degré. Le discriminant de cette équation est $1-4z$. Continuant formellement les calculs, il vient pour $z$ non nul\n",
    "\n",
    "$$f(z)=\\frac{1\\pm\\sqrt{1-4z}}{2z}$$\n",
    "\n",
    "Des considérations de continuité pour la fonction $f$ montrent que le signe $\\pm$ est le même pour tout $z$. Toujours pour des raisons de continuité, la fonction $f$ est bornée au voisinage de 0. Le numérateur de la fraction tend donc vers 0 lorsque $z$ tend vers 0. Ainsi, \n",
    "\n",
    "$$f(z)=\\frac{1-\\sqrt{1-4z}}{2z}$$\n",
    "\n",
    "Développons $\\sqrt{1-4z}$ en série entière.\n",
    "\n",
    "$$\\sqrt{1-4z}=\\sum_{n=0}^\\infty (-4)^nz^n\\binom{\\frac 1 2}{n}$$\n",
    "\n",
    "où $\\binom{\\frac 1 2} 0=1$, et\n",
    "\n",
    "$$\\binom{\\frac 1 2} n=\\frac{\\frac 1 2\\left(\\frac 1 2 - 1\\right)\\ldots\\left(\\frac 1 2 - n+1\\right)}{n!}$$\n",
    "\n",
    "si $n\\ge 1$. Le lecteur est invité à vérifier que si $n\\ge 1$,\n",
    "\n",
    "$$\\binom{\\frac 1 2} n=\\frac{(-1)^{n-1}}{2^{2n-1}}\\frac 1 n\\binom{2n-2}{n-1}$$\n",
    "\n",
    "On en déduit après quelques simplifications que\n",
    "\n",
    "$$f(z)=\\sum_{n=0}^\\infty\\frac{1}{n+1}\\binom{2n}nz^n$$\n",
    "\n",
    "Par unicité de l'écriture d'une série entière on en déduit que pour tout $n\\in\\mathbb N$,\n",
    "\n",
    "$$C_n=\\frac{1}{n+1}\\binom{2n}n$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Les entiers $C_n$ sont appelés les __nombres de Catalan__. \n",
    "\n",
    "__Exercice__ : En utilisant la formule de Stirling, montrer que\n",
    "\n",
    "$$C_n\\sim\\frac{4^n}{n\\sqrt{\\pi n}}$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def catalan(n):\n",
    "    p = 1\n",
    "    for k in range(n):\n",
    "        p *= (2 * n - k)\n",
    "    for k in range(n):\n",
    "        p = p // (k + 1)\n",
    "    return p // (n + 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print([catalan(k) for k in range(15)])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 4.2 Critique de la fonction `random_abr`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Rappelez-vous la fonction `random_abr` : on insère dans un ABR initialement vide une permutation aléatoire des entiers de 0 à $n-1$. Combien y a-t-il de telles permutations ? Il y en a $n!$. Mais $C_n=o(n!)$, beaucoup de permutations différentes fournissent le même ABR \"aléatoire\".\n",
    "\n",
    "Regardez la fonction `inserer`. En partant d'un arbre initialement vide et en y insérant des objets, c'est le premier objet inséré qui est la racine de l'arbre final.\n",
    "\n",
    "__Question 1__ : Quelle est la probabilité que la fonction `random_abr` renvoie un ABR dont la racine est 0 ?\n",
    "\n",
    "__Réponse__ : C'est la probabilité qu'une permutation $s$ des entiers $0, \\ldots, n-1$ vérifie $s[0]=0$, c'est à dire $\\frac 1 n$.\n",
    "\n",
    "__Question 2__ : On met la probabilité uniforme sur l'ensemble des ABR dont les noeuds sont $0,\\ldots,n-1$. Quelle est la probabilité qu'un ABR ait pour racine 0 ?\n",
    "\n",
    "__Réponse__ : Les ABR qui nous intéressent sont ceux qui ont un fils gauche vide et un fils droit qui est un ABR de taille $n-1$ dont les noeuds sont $1,2,\\ldots,n-1$. Il y en a $C_{n-1}$. La probabilité qu'un ABR soit de ce type est donc\n",
    "\n",
    "$$\\frac{C_{n-1}}{C_n}$$\n",
    "\n",
    "Par un calcul direct à partir de l'expression des nombres de Catalan, on voit que cette probabilité est\n",
    "\n",
    "$$\\frac{n+1}{2(2n-1)}\\sim\\frac 1 4$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Cela ne correspond pas du tout à la probabilité qui concerne la fonction `random_abr` ! La fonction `random_abr` ne renvoie donc pas un ABR aléatoire."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 4.3 Quelle est la racine d'un ABR aléatoire ?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Histoire de bien voir que notre fonction `random_abr` est très mauvaise, quelle est la probabilité que la racine d'un ABR aléatoire ait une certaine valeur ? Quelle est la racine la plus probable ? La moins probable ?\n",
    "\n",
    "Supposons que l'ensemble des noeuds est l'ensemble des entiers entre 0 et $n-1$. Soit $0\\le k\\le n-1$. Quelle est la probabilité qu'un ABR ait $k$ pour racine ? Il y a $C_k$ fils gauches possibles et $C_{n-1-k}$ fils droits possibles. La probabilité cherchée est donc\n",
    "\n",
    "$$p_k=\\frac{C_kC_{n-1-k}}{C_n}$$\n",
    "\n",
    "Pas question de rechercher le minimum et le maximum de cette quantité. Contentons-nous d'une simulation numérique. En bleu, la probabilité (constante) qu'un arbre __renvoyé par `random_abr`__ ait $k$ pour racine. En rouge, la probabilité réelle."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "n = 20\n",
    "cs = [catalan(k) for k in range(n + 1)]\n",
    "s = [cs[k] * cs[n - 1 - k] / cs[n] for k in range(n)]\n",
    "s1 = n * [1 / n]\n",
    "plt.plot(s, 'k')\n",
    "plt.plot(s, 'or')\n",
    "plt.plot(s1, 'k')\n",
    "plt.plot(s1, 'ob')\n",
    "plt.grid()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "La probabiité maximale survient pour $k=0$ et $k=n-1$. Il y a plus d'une chance sur 2 que la racine d'un ABR aléatoire n'ait qu'un fils ! La probabilité minimale a l'air de survenir pour $k$ environ égal à $\\frac n 2$ ... et, définitivement, la fonction `random_abr` ne renvoie pas un ABR aléatoire."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 4.4 Mais alors, comment fabriquer un ABR aléatoire ?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Commençons par le résultat suivant :\n",
    "\n",
    "__Proposition__ Soit $t$ un arbre binaire à $n$ noeuds. Soit $E$ un ensemble totalement ordonné ayant $n$ éléments. Il existe un et un seul étiquetage des noeuds de $t$ par les éléments de $E$ qui fasse de $t$ un ABR.\n",
    "\n",
    "__Démonstration__ : On fait une récurrence sur $n$.\n",
    "\n",
    "- Si $n=0$ c'est évident vu qu'il n'y a rien à étiqueter.\n",
    "- Soit $n\\ge 0$. Supposons la propriété vraie pour tous les entiers inférieurs ou égaux à $n$. Soit $t$ un arbre binaire à $n+1$ noeuds. Soit $E=\\{x_0,\\ldots,x_n\\}$ un ensemble totalement ordonné, où $x_0<\\ldots<x_n$. Soit $k$ le nombre de noeuds du fils gauche de $t$, $0\\le k \\le n$. La racine de $t$ doit être supérieure à $k$ éléments de $E$ et inférieure à $n-k$ éléments de $E$. La racine de $t$ est donc $x_k$.\n",
    "\n",
    "Il faut ensuite\n",
    "\n",
    "- Étiqueter le fils gauche de $t$ avec $x_0,\\ldots,x_{k-1}$. Par l'hypothèse de récurrence il y a une et une seule façon de faire cela.\n",
    "- Étiqueter le fils droit de $t$ avec $x_{k+1},\\ldots,x_{n}$. Par l'hypothèse de récurrence il y a une et une seule façon de faire cela.\n",
    "\n",
    "On a donc bien un et un seul étiquetage qui fasse de $t$ un ABR.\n",
    "\n",
    "Voici la fonction d'étiquetage. Elle suppose que l'ensemble $E$ est donné par la liste de ses éléments __dans l'ordre croissant__."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def etiqueter(t, E):\n",
    "    if est_vide(t): return vide()\n",
    "    else:\n",
    "        u, v = fg(t), fd(t)\n",
    "        k = nombre_noeuds(u)\n",
    "        u1 = etiqueter(u, [e for e in E if e < E[k]])\n",
    "        v1 = etiqueter(v, [e for e in E if e > E[k]])\n",
    "        return arbre(E[k], u1, v1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Comment tester cette fonction ? Idée, fabriquons un ABR \"aléatoire\" avec `random_abr`. Puis effaçons ses noeuds. Enfin appelons `etiqueter`. On devrait retrouver l'ABR de départ !"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def effacer(t, z):\n",
    "    if est_vide(t): return vide()\n",
    "    else:\n",
    "        u, v = fg(t), fd(t)\n",
    "        u1 = effacer(u, z)\n",
    "        v1 = effacer(v, z)\n",
    "        return arbre(z, u1, v1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "t = random_abr(100)\n",
    "dessiner(t)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "t1 = effacer(t, 0)\n",
    "dessiner(t1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "t2 = etiqueter(t1, list(range(100)))\n",
    "dessiner(t2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(t == t2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Conséquence__ : Pour fabriquer un ABR aléatoire dont les noeuds sont les éléments de $E$, de cardinal $n$ :\n",
    "\n",
    "1. On fabrique un arbre aléatoire (pas forcément \"de recherche\") ayant $n$ noeuds.\n",
    "2. On étiquette cet arbre avec les éléments de $E$, il y a une seule façon de faire cela.\n",
    "\n",
    "Reste à savoir comment fabriquer un arbre binaire aléatoire. Ceci est un sujet à part entière. Si vous voulez vraiment savoir, consultez le notebook intitulé \"arbres binaires aléatoires\" ..."
   ]
  }
 ],
 "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
}