{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Arbres binaires"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Marc Lorenzi - 18 avril 2018"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import matplotlib.pyplot as plt\n",
    "%matplotlib inline\n",
    "import random, sys, timeit\n",
    "from math import log"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 1. Notion d'arbre binaire"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.1 C'est quoi ?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Un arbre binaire est une structure de données qui est soit `None`, soit un triplet $t=(x, t_1, t_2)$ où $x$ est un objet et $t_1$ et $t_2$ sont des arbres.\n",
    "\n",
    "- $x$ est la racine de $t$\n",
    "- $t_1$ est le fils gauche de $t$\n",
    "- $t_2$ est le fils droit de $t$\n",
    "\n",
    "L'arbre `None` sera appelé __l'arbre vide__."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Les fonctions ci-dessous explicitent ces définitions."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def racine(t): return t[0]\n",
    "def gauche(t): return t[1]\n",
    "def droit(t): return t[2]\n",
    "def fils(t): return (gauche(t), droit(t))\n",
    "\n",
    "def est_vide(t): return t == None"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Jusqu'à ce que nous puissions faire mieux, voici un arbre que nous utiliserons pour tester nos fonctions."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "exemple = (5, (3, (2, (0, None, (1, None, None)), None), (4, None, None)), \n",
    "(14, (6, None, (12, (8, (7, None, None), (10, (9, None, None), (11, None, None))), \n",
    "(13, None, None))), (17, (16, (15, None, None), None), (18, None, (19, None, None)))))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(exemple)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tous ces \"None\" sont un peu embêtants, écrivons une fonction qui affiche de façon plus claire un arbre."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.3 Afficher joliment un arbre"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Si les deux fils de l'arbre $t$ sont vides, affichons juste sa racine. Et si l'arbre est vide affichons une étoile. Sinon, $t=(x, t_1, t_2)$. Affichons $x(s_1, s_2)$ où $s_i$ est la représentation de $t_i$.  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def vers_chaine(t):\n",
    "    if est_vide(t): return '*'\n",
    "    else:\n",
    "        x, t1, t2 = t\n",
    "        if est_vide(t1) and est_vide(t2): return str(x)\n",
    "        else:\n",
    "            s1 = str(x) + '('\n",
    "            s2 = vers_chaine(t1) + ','\n",
    "            s3 = vers_chaine(t2) + ')'\n",
    "            return s1 + s2 + s3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def print_tree(t):\n",
    "    print(vers_chaine(t))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print_tree(exemple)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "C'est un peu mieux mais pas encore idéal. On va faire beaucoup mieux un peu plus loin."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.3 Noeuds, feuilles"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Définition (Noeud)__ : Soit $t$ un arbre. Si $t$ est vide, alors $t$ n'a pas de noeud. Sinon, $t=(x,t_1,t_2)$ où $t_1$ et $t_2$ sont des arbres. Un noeud de $t$ est alors $x$ ou un noeud de $t_1$ ou un noeud de $t_2$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "À titre d'exemple, écrivons une fonction qui calcule le nombre de noeuds d'un arbre."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def nombre_noeuds(t):\n",
    "    if est_vide(t): return 0\n",
    "    else:\n",
    "        _, t1, t2 = t\n",
    "        return nombre_noeuds(t1) + nombre_noeuds(t2) + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "nombre_noeuds(exemple)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Définition (Feuille)__ : soit $t$ un arbre. Si $t$ est vide alors $t$ n'a pas de feuille. Sinon,  $t=(x,t_1,t_2)$ où $t_1$ et $t_2$ sont des arbres. Si $t_1$ et $t_2$ sont vides alors $x$ est une feuille de $t$. Sinon, les feuilles de $t$ sont les feuilles de $t_1$ ou les feuilles de $t_2$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def nombre_feuilles(t):\n",
    "    if est_vide(t): return 0\n",
    "    else:\n",
    "        _, t1, t2 = t\n",
    "        if est_vide(t1) and est_vide(t2): return 1\n",
    "        else: return nombre_feuilles(t1) + nombre_feuilles(t2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "nombre_feuilles(exemple)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Quelles sont les feuilles de notre exemple ? Le plus simple est d'écrire une fonction qui renvoie la liste des feuilles d'un arbre."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def liste_feuilles(t):\n",
    "    if est_vide(t): return []\n",
    "    else:\n",
    "        x, t1, t2 = t\n",
    "        if est_vide(t1) and est_vide(t2): return [x]\n",
    "        else: return liste_feuilles(t1) + liste_feuilles(t2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "liste_feuilles(exemple)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.4 Hauteur d'un arbre"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Définition (Hauteur)__ : Soit $t$ un arbre. Si $t$ est vide, sa hauteur est 0. Sinon, $t=(x,t_1,t_2)$ où $t_1$ et $t_2$ sont des arbres. La hauteur de $t$ est alors 1 + le max de la hauteur de $t_1$ et de la hauteur de $t_2$.\n",
    "\n",
    "Ou, si on préfère : la hauteur de $t$ est la longueur du plus long chemin de sa racine à l'une de ses feuilles."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def hauteur(t):\n",
    "    if est_vide(t): return 0\n",
    "    else:\n",
    "        _, t1, t2 = t\n",
    "        return max([hauteur(t1), hauteur(t2)]) + 1 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "hauteur(exemple)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2. Dessiner un arbre"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Ce serait tout de même mieux d'avoir une vision graphique de nos arbres. La fonction `draw_tree` ci-dessous fait le travail. Pour dessiner un arbre :\n",
    "\n",
    "- On dessine son fils gauche\n",
    "- On dessine son fils droit\n",
    "- On trace un trait de la racine au fils gauche\n",
    "- On trace un trait de la racine au fils droit\n",
    "\n",
    "Si l'arbre est vide on ne dessine rien. Mieux vaut éviter d'exécuter la fonction `draw_tree` avec des arbres qui ont, disons, plus d'un millier de noeuds, sous peine d'attendre longtemps avant de voir quelque chose s'afficher."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "La fonction `draw_tree_aux` ci-dessous prend quatre paramètres :\n",
    "\n",
    "- Un arbre $t$\n",
    "- Une rectangle $rect$. Si $rect=(x_1, x_2, y_1, y_2)$, l'arbre $t$ est dessiné dans le rectangle $[x_1,x_2]\\times[y_1,y_2]$.\n",
    "- Un entier $dy$ : c'est la distance entre deux niveaux de l'arbre.\n",
    "- Un paramètre `labels` qui est égal à True par défaut. S'il vaut True, les valeurs des noeuds sont affichées. Sinon, seul le \"squelette\" de l'arbre est affiché. Il n'est pas évident de positionner correctement les étiquette des noeuds. On peut faire mieux que ci-dessous mais pour garder un code simple on va se contenter de ça.\n",
    "\n",
    "On ne va pas utiliser cette fonction directement, elle sera appelée par la fonction principale `draw_tree`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def draw_tree_aux(t, rect, dy, labels):\n",
    "    if est_vide(t): return\n",
    "    x1, x2, y1, y2 = rect\n",
    "    xm = (x1 + x2) // 2\n",
    "    x, t1, t2 = t\n",
    "    draw_tree_aux(t1, (x1, xm, y1, y2 - dy), dy, labels)\n",
    "    draw_tree_aux(t2, (xm, x2, y1, y2 - dy), dy, labels)\n",
    "    if labels: plt.text(xm + 10, y2, str(x), fontsize=10, 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='s')\n",
    "    if not est_vide(t2):\n",
    "        c, d = ((xm, (x2 + xm) // 2), (y2, y2 - dy))\n",
    "        plt.plot(c, d, 'k', marker='s')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Voici la fonction de tracé. Elle prend un arbre $t$ en paramètre. Elle initialise un rectangle sympa (en fait un carré) où tracer l'arbre. Elle calcule la distance idéale entre le tracé de deux niveaux de l'arbre. Cette distance dépend bien entendu de la hauteur de l'arbre $t$. Enfin elle appelle `draw_tree_aux`. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def draw_tree(t, labels=True):\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, labels)\n",
    "    plt.axis([0, d, 0, d])\n",
    "    plt.axis('off')\n",
    "    plt.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "draw_tree(exemple, labels=True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "draw_tree(exemple, labels=False)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2. Arbres binaires de recherche"
   ]
  },
  {
   "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 facile de retrouver un noeud. On les appelle des arbres binaires de recherche (ABR en abrégé). Ce sont les arbres vérifiant, pour chaque noeud $x$ de l'arbre, que les noeuds du fils gauche de $x$ sont inférieurs ou égaux à $x$, et les noeuds du fils droit de ce même $x$ sont strictement supérieurs à $x$. On convient également que l'arbre vide est un ABR."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Notre `exemple` est un ABR ! Quelle chance ..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "draw_tree(exemple)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.1 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, t1, t2 = t\n",
    "        if x < y: return rechercher(x, t1)\n",
    "        elif x > y: return rechercher(x, t2)\n",
    "        else: return True"
   ]
  },
  {
   "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) 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 mais nous n'en parlerons pas ici. 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 None\n",
    "    else:\n",
    "        t = arbre_pas_equilibre_du_tout(n - 1)\n",
    "        return (n, t, None)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "draw_tree(arbre_pas_equilibre_du_tout(10))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.2 Et maintenant ?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Un arbre binaire de recherche peut être vu comme une structure qui permet de stocker un ensemble de données. Où cela ? Dans les noeuds, bien entendu. Nous venons de voir comment rechercher une donnée dans cet ensemble efficacement (si tout va bien). Cela dit, les ensembles de données ne sont intéressants que s'ils peuvent évoluer au cours du temps. On veut pouvoir ajouter et supprimer des éléments dans l'ensemble ! Il doit être une structure de données __dynamique__. Les trois opérations fondamentales sur une structure d'ensemble dymamique sont :\n",
    "\n",
    "- RECHERCHER\n",
    "- INSERER\n",
    "- SUPPRIMER\n",
    "\n",
    "On voit à peu près ce qu'il nous reste à faire."
   ]
  },
  {
   "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, None, None)\n",
    "    else:\n",
    "        y, t1, t2 = t\n",
    "        if x <= y: return (y, inserer(x, t1), t2)\n",
    "        else: return (y, t1, inserer(x, t2))"
   ]
  },
  {
   "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.3 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$. Étudiez son code, il est facile à comprendre.\n",
    "\n",
    "On peut __montrer__ que `random_list` renvoie effectivement toute permutation de la liste $[0,\\ldots,n-1]$ avec une probabilité égale à $\\frac 1 {n!}$. Cette fonction mérite donc bien son nom. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def random_list(n):\n",
    "    s = list(range(n))\n",
    "    for k in range(n):\n",
    "        i = random.randint(0, k)\n",
    "        s[i], s[k] = s[k], s[i]\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",
    "print_tree(t)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "draw_tree(t, labels=True)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Nous pouvons (VOUS pouvez) 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_feuilles(random_abr(10000))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Le résultat renvoyé par la fonction précédente est assez rassurant : il est connu que dans un ABR aléatoire environ $\\frac 1 3$ des noeuds sont des feuilles (alors que dans un arbre aléatoire quelconque, $\\frac 1 4$ environ des noeuds sont des feuilles)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.4 Intermède : arbres binaires quelconques aléatoires (essai) "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Comment créer un arbre binaire aléatoire quelconque ? Intéressons nous seulement à la forme des arbres, et pas à la valeur des noeuds. Voici une idée : partant d'un arbre vide, on insère $n$ fois au hasard un noeud dans l'arbre. Comment insérer au hasard ? Eh bien on lance une pièce. Si c'est pile, on insère au hasard dans le fils gauche. Si c'est face, on insère au hasard dans le fils droit."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def inserer_hasard(x, t):\n",
    "    if est_vide(t): return (x, None, None)\n",
    "    else:\n",
    "        y, t1, t2 = t\n",
    "        r = random.randint(0, 1)\n",
    "        if r == 0: return (y, inserer_hasard(x, t1), t2)\n",
    "        else: return (y, t1, inserer_hasard(x, t2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def random_tree(n):\n",
    "    t = None\n",
    "    for k in range(n):\n",
    "        t = inserer_hasard(0, t)\n",
    "    return t"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "t = random_tree(100)\n",
    "draw_tree(t, labels=False)\n",
    "print(nombre_feuilles(t))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Certains détail nous chiffonnent. Exécutez plusieurs fois la cellule précédente : les arbres ont l'air trop équilibrés. Et puis un peu plus haut il est écrit que dans un arbre binaire à $n$ noeuds, le nombre moyen de feuilles est $\\frac n 4$. C'est loin d'être ce que nous observons sur nos arbres \"aléatoires\". En réalité, créer un arbre vraiment aléatoire est plus subtil que cela. Nous n'irons pas plus avant dans ce notebook."
   ]
  },
  {
   "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, _, t2 = t\n",
    "        if est_vide(t2): return x\n",
    "        else: return maximum(t2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "maximum(random_abr(1000))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Pour la fonction suivante je refuse d'expliquer."
   ]
  },
  {
   "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, t1, _ = t\n",
    "        if est_vide(t1): return x\n",
    "        else: return minimum(t1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "minimum(random_abr(1000))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.6 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": [
    "draw_tree(exemple)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Par exemple, le plus proche ancêtre commun de 12 et 16 est 14. 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, t1, t2 = t\n",
    "        if x < y: return (y, supprimer(x, t1), t2)\n",
    "        elif x > y: return (y, t1, supprimer(x, t2))\n",
    "        elif est_vide(t2): return t1\n",
    "        else:\n",
    "            m = minimum(t2)\n",
    "            return (m, t1, supprimer(m, t2))\n",
    "            "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Testons. Je ne commente pas les résultats, vu qu'ils changent à chaque exécution. À vous de voir exactement ce qui se passe, plusieurs fois de suite."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "t = random_abr(10)\n",
    "draw_tree(t)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "draw_tree(supprimer(4, t))"
   ]
  },
  {
   "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": [
    "draw_tree(exemple)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Les ancêtres de 13 (au sens large) sont : 13, 12, 6, 14, 5. Le successeur de 13 est 14 parce que la racine du fils gauche de 14 est 6, qui est encore un ancêtre de 13. Et 14 est le plus proche ancêtre de 13 à vérifier cette propriété.\n",
    "\n",
    "Dit autrement, on part de 13, on monte à gauche, puis à gauche, etc. Au premier virage à droite on est arrivés. Bref, c'est au fond à droite en montant."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 3. Parcourir un arbre binaire"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Parcourir un arbre, c'est explorer, visiter, tous ses noeuds. Pour quoi faire ? Tout un tas de choses. En réalité, un grand nombre des fonctions que nous avons écrites exploraient des arbres : hauteur, nombre de noeuds, affichage, etc. Il existe plusieurs façons de parcourir un arbre, dont, entre-autres :\n",
    "\n",
    "- Le parcours niveau par niveau. Racine, puis fils de la racine, puis petits-fils, etc.\n",
    "- Le parcours préfixe : on visite la racine, puis on parcourt le fils gauche, puis on parcourt le fils droit.\n",
    "- Le parcours suffixe : on parcourt le fils gauche, puis on parcourt le fils droit, puis on visite la racine.\n",
    "- Le parcours infixe : on parcourt le fils gauche, puis on visite la racine, puis on parcourt le fils droit.\n",
    "\n",
    "Je ne parlerai pas ici du parcours par niveau qui nécessite d'utiliser une structure de données auxiliaire (une __file d'attente__). Le parcours par niveau est aussi appelé __parcours en largeur__. On visite les noeuds à distance 1 de la racine, puis ceux à distance 2, etc.\n",
    "\n",
    "Ci-dessous, deux fonctions qui effectue un parcours préfixe et un parcours infixe d'un arbre $t$ en affichant ses noeuds."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def parcours_prefixe(t):\n",
    "    if est_vide(t): return\n",
    "    else:\n",
    "        x, t1, t2 = t\n",
    "        sys.stdout.write(str(x) + ' ')\n",
    "        parcours_prefixe(t1)\n",
    "        parcours_prefixe(t2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "parcours_prefixe(random_abr(30))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def parcours_infixe(t):\n",
    "    if est_vide(t): return\n",
    "    else:\n",
    "        x, t1, t2 = t\n",
    "        parcours_infixe(t1)\n",
    "        sys.stdout.write(str(x) + ' ')\n",
    "        parcours_infixe(t2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "parcours_infixe(random_abr(30))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tiens, dans le deuxième cas c'est rangé dans l'ordre. Eh oui, puisque l'arbre en paramètre est un ABR. Ce nous ouvre des perspectives insoupçonnées. Lesquelles ? Réfléchissez avant de lire la fin."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Plutôt que d'afficher, écrivons une fonction qui prend un arbre en paramètre et renvoie la liste de ses sommets visités selon un parcours infixe."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def arbre_vers_liste(t):\n",
    "    if est_vide(t): return []\n",
    "    else:\n",
    "        x, t1, t2 = t\n",
    "        return arbre_vers_liste(t1) + [x] + arbre_vers_liste(t2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(arbre_vers_liste(random_abr(30)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Voici la \"réciproque\" de cette fonction."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def liste_vers_arbre(s):\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": [
    "draw_tree(liste_vers_arbre(random_list(20)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "draw_tree(liste_vers_arbre(range(10)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 4. Un algorithme de tri"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 4.1 L'algorithme"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Nous y voilà. Un bon article sur les structures de données se termine toujours par un algorithme de tri absolument nouveau et redoutablement efficace :-). Le voici :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def trier(s):\n",
    "    return arbre_vers_liste(liste_vers_arbre(s))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Eh oui, on prend la liste $s$, on fabrique un ABR dont les noeuds sont ses éléments, on renvoie la liste des noeuds de l'ABR avec un parcours infixe. On a trié la liste $s$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "s = random_list(20)\n",
    "print(s)\n",
    "print(trier(s))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Cet algorithme est-il efficace ? Sa complexité peut être mauvaise, $O(n^2)$ en fait (où $n$ est la longueur de la liste à trier), si l'arbre créé est déséquilibré. Par exemple si, ironie du sort, la liste à trier est déjà triée (voir le dessin ci-dessus). Mais on peut montrer qu'en moyenne la complexité de cet algorithme est un $O(n\\log n)$ où $n$ est le nombre d'éléments de la liste. En réalité cet algorithme n'a rien de nouveau, c'est tout simplement une variante déguisée (et pas très optimisée) de l'algorithme du tri rapide."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 4.2 Simulations"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Quel est le temps réel mis par notre algorithme pour trier une liste ?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%%time\n",
    "s = random_list(10000)\n",
    "trier(s)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "On peut faire mieux en stockant dans une liste les temps mis pour trier des listes de tailles 10000, 20000, ..., 100000. Soyez un peu patients en exécutant les lignes ci-dessous !"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "s = []\n",
    "for k in range(1, 11):\n",
    "    n = 10000 * k\n",
    "    t = timeit.timeit('trier(random_list(%d))' % n, setup='from __main__ import trier, random_list', number=1)\n",
    "    s.append(t)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "plt.plot(s, 'k-')\n",
    "plt.grid()\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Graphique pas très parlant, mais la théorie nous dit que si $T(n)$ est le temps moyen mis pour trier une liste de taille $n$, alors $T(n)\\sim C n\\ln n$ où $C>0$ est un réel qui dépend de beaucoup de choses, de la machine utilisée entre-autres. Comment trouver $C$ ? Eh bien on devrait avoir $C\\simeq \\frac{T(100000)}{100000\\ln 100000}$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "C = s[9] / (100000 * log(100000))\n",
    "print(C)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Regardons si ça colle."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "s1 = [C * (10000 * k) * log(10000 * k) for k in range(1, 11)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "plt.plot(s)\n",
    "plt.plot(s1)\n",
    "plt.grid()\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Ça colle, enfin à peu près. Et je décrète que c'est la fin :-)."
   ]
  }
 ],
 "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
}