{
"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"
],
"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"
],
"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
}