{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Arbres Binaires de Recherche\n", "\n", "### Motivation\n", "\n", "A quoi servent les arbres binaires de recherche ?\n", "\n", "\n", "### Définition (Arbre binaire de recherche)\n", "*N'hésitez pas à ajouter des définitions préliminaires.*\n", "\n", "### Exemples\n", "\n", "*Donner au moins un exemple et un contre-exemple*\n", "\n", "### Implémentation\n", "\n", "Implanter les fonctions `taille`, `profondeur`, `est_present`, `insertion`, `est_binaire_de_recherche` dans la classe Noeud. Les tester sur des exemples." ] }, { "cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [], "source": [ "class Noeud:\n", " def __init__(self, cle, gauche = None, droit = None):\n", " self.cle = cle\n", " if gauche != None:\n", " if not isinstance(gauche, Noeud):\n", " raise TypeError(\"gauche doit être un Noeud, pas %s\" % gauche)\n", " self.gauche = gauche\n", " else:\n", " self.gauche = None\n", " if droit != None:\n", " if not isinstance(droit, Noeud):\n", " raise TypeError(\"droit doit être un Noeud, pas %s\" % droit)\n", " self.droit = droit\n", " else:\n", " self.droit = None\n", "\n", " def __repr__(self):\n", " return \"Noeud(\\t%s,\\n\\t%s,\\n\\t%s\\n)\" % (self.gauche.__repr__(), self.cle, self.droit.__repr__())\n", "\n", " def __str__(self):\n", " return \"Noeud(%s)\" % self.cle\n", "\n", " def possede_enfant_gauche(self):\n", " \"\"\" Noeud -> bool\n", " Renvoie vrai si et seulement si self possède un enfant à gauche\"\"\"\n", " return self.gauche != None\n", "\n", " def possede_enfant_droit(self):\n", " \"\"\" Noeud -> bool\n", " Renvoie vrai si et seulement si self possède un enfant à droite\"\"\"\n", " return self.droit != None\n", "\n", " def export_vers_dot(self):\n", " \"\"\" Noeud -> str\n", " Renvoie la description au format dot du noeud et de ses enfants\"\"\"\n", " s = \"\"\n", " if self.possede_enfant_gauche():\n", " s += '\"%s\" -> \"%s\";\\n' % (str(self), str(self.gauche))\n", " s += self.gauche.export_vers_dot()\n", " if self.possede_enfant_droit():\n", " s += '\"%s\" -> \"%s\";\\n' % (str(self), str(self.droit))\n", " s += self.droit.export_vers_dot()\n", " return s\n", "\n", " \n", " def taille(self):\n", " \"\"\" \"\"\"\n", " return NotImplemented\n", " \n", " def profondeur(self):\n", " \"\"\" \"\"\"\n", " return NotImplemented\n", " \n", " def est_present(self, cle):\n", " \"\"\" \"\"\"\n", " \n", " def insertion(self, cle):\n", " \"\"\" \"\"\"\n", " # l'implémentation suivante est fausse, mais elle permet de créer des arbres.\n", " courant = self\n", " while(courant.gauche is not None):\n", " courant = courant.gauche\n", " courant.gauche = Noeud(cle)\n", " \n", " def est_binaire_de_recherche():\n", " \"\"\" \"\"\"\n", " return NotImplemented\n", " \n", " \n", "\n", "class ArbreBinaireRecherche:\n", " def __init__(self, *args):\n", " self.racine = None\n", "\n", " if len(args) == 1:\n", " if isinstance(args[0], Noeud):\n", " self.racine = args[0]\n", " else:\n", " for e in args[0]:\n", " self.insertion(e)\n", "\n", " def export_vers_dot(self):\n", " \"\"\" ArbreBinaireRecherche -> str\n", " Renvoie la description au format dot de l'Arbre Binaire\"\"\"\n", " return \"digraph BST{\\n%s}\" % self.racine.export_vers_dot()\n", "\n", " def insertion(self, cle):\n", " \"\"\" ArbreBinaireRecherche -> ()\n", " Insère cle dans l'ArbreBinaireRecherche self\"\"\"\n", " if self.racine == None:\n", " self.racine = Noeud(cle)\n", " else:\n", " self.racine.insertion(cle)\n", "\n", " def taille(self):\n", " \"\"\" ArbreBinairerecherche -> int\n", " Renvoie la taille de l'arbre self\"\"\"\n", " return self.racine.taille()\n", "\n", " def profondeur(self):\n", " \"\"\" Arbrebinairerecherche -> int\n", " Renvoie la profondeur de l'arbre self\"\"\"\n", " return self.racine.profondeur()" ] }, { "cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [], "source": [ "# Il y a deux manières de construires des arbres binaires de recherche\n", "# Soit en donnant la liste des clés, qui sont ensuite insérées une par une dans l'arbre\n", "# Soit en donnant un noeud qui sera la racine de l'arbre\n", "arbre1 = ArbreBinaireRecherche([0,1,2])\n", "arbre2 = ArbreBinaireRecherche([12,10,14,9,11,13,15])\n", "arbre3 = ArbreBinaireRecherche(Noeud(1, Noeud(0), Noeud(2)))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Export vers dot\n", "\n", "Tester le code ci-dessous. S'il ne marche pas, essayer un site tel que [GraphViz Online](https://dreampuf.github.io/GraphvizOnline/) (avec le contenu de `texte_dot` par exemple`)." ] }, { "cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Texte descriptif dot: digraph BST{\n", "\"Noeud(1)\" -> \"Noeud(0)\";\n", "\"Noeud(1)\" -> \"Noeud(2)\";\n", "}\n" ] }, { "data": { "image/svg+xml": [ "\n", "\n", "\n", "\n", "\n", "\n", "BST\n", "\n", "\n", "\n", "Noeud(1)\n", "\n", "Noeud(1)\n", "\n", "\n", "\n", "Noeud(0)\n", "\n", "Noeud(0)\n", "\n", "\n", "\n", "Noeud(1)->Noeud(0)\n", "\n", "\n", "\n", "\n", "\n", "Noeud(2)\n", "\n", "Noeud(2)\n", "\n", "\n", "\n", "Noeud(1)->Noeud(2)\n", "\n", "\n", "\n", "\n", "\n" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "from graphviz import Source\n", "\n", "texte_dot = arbre3.export_vers_dot()\n", "print(\"Texte descriptif dot: %s\" % texte_dot)\n", "dot = Source(texte_dot)\n", "display(dot)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Complexité\n", "\n", "Quelle est la complexité de `recherche`, `insertion` ?" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Arbres Rouge-Noir\n", "\n", "### Motivation\n", "Quels sont les avantages et les inconvénients des arbres rouge-noir par rapport aux arbres binaires de recherche ?\n", "\n", "\n", "### Définition (Arbre rouge-noir)\n", "*N'hésitez pas à ajouter des définitions préliminaires.*\n", "\n", "### Profondeur maximale \n", "Considérons un arbre rouge-noir avec $n$ noeuds. Quelle est sa profondeur maximale (le prouver) ?\n", "\n", "### Exemples\n", "*Donner au moins un exemple et un contre-exemple*\n", "\n", "### Implémentation\n", "Implanter les fonctions `taille_noire`, `est_rouge_noir`, `insertion`. Les tester sur des exemples." ] }, { "cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [], "source": [ "class NoeudRN(Noeud):\n", " def __init__(self, cle, est_noir = True, gauche = None, droit = None):\n", " super().__init__(cle, gauche, droit)\n", " if isinstance(est_noir, bool):\n", " self.est_noir = est_noir\n", " else:\n", " raise TypeError(\"est_noir doit être un booléen, pas %s\" % est_noir)\n", " \n", " def __repr__(self):\n", " if self.est_noir:\n", " return \"NoeudN(\\t%s,\\n\\t%s,\\n\\t%s\\n)\" % (self.gauche.__repr__(), self.cle, self.droit.__repr__()) \n", " else:\n", " return \"NoeudR(\\t%s,\\n\\t%s,\\n\\t%s\\n)\" % (self.gauche.__repr__(), self.cle, self.droit.__repr__())\n", " \n", " def __str__(self):\n", " return \"NoeudRN(%s)\" % self.cle\n", " \n", " def export_vers_dot(self):\n", " \"\"\" NoeudRN -> str\n", " Renvoie la description au format dot du noeud et de ses enfants\"\"\"\n", " s = \"\"\n", " if not self.est_noir:\n", " s += '\"%s\"[style=filled, color=\"red\"];\\n' % str(self)\n", " if self.possede_enfant_gauche():\n", " s += '\"%s\" -> \"%s\";\\n' % (str(self), str(self.gauche))\n", " s += self.gauche.export_vers_dot()\n", " if self.possede_enfant_droit():\n", " s += '\"%s\" -> \"%s\";\\n' % (str(self), str(self.droit))\n", " s += self.droit.export_vers_dot()\n", " return s\n", " \n", " def taille_noire(self):\n", " \"\"\" \"\"\"\n", " \n", " def est_rouge_noir():\n", " \"\"\" \"\"\"\n", " \n", " def insertion(self, cle):\n", " \"\"\" \"\"\"\n", "\n", "class ArbreRougeNoir(ArbreBinaireRecherche):\n", " def insertion(self, cle):\n", " \"\"\" ArbreRougeNoir -> ()\n", " Insère cle dans l'ArbreBinaireRecherche self\"\"\"\n", " if self.racine == None:\n", " self.racine = NoeudRN(cle)\n", " else:\n", " self.racine.insertion(cle)\n", " \n", " def taille_noire(self):\n", " \"\"\" ArbreRougeNoir -> int\n", " Renvoie la taille noire depuis la racine\"\"\"\n", " return self.racine.taille_noire()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Exemples" ] }, { "cell_type": "code", "execution_count": 5, "metadata": {}, "outputs": [ { "data": { "image/svg+xml": [ "\n", "\n", "\n", "\n", "\n", "\n", "BST\n", "\n", "\n", "\n" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "arbre = ArbreRougeNoir([0, 1, 2])\n", "\n", "dot = Source(arbre.export_vers_dot())\n", "display(dot)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Complexité\n", "\n", "Quelle est la complexité de l'insertion ? Pourquoi ?\n", "\n", "La fonction recherche définie sur les noeuds non-colorés fonctionne-t-elle ici ? Quelle est sa complexité ?" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Bibliographie" ] } ], "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.7.1" } }, "nbformat": 4, "nbformat_minor": 2 }