Algorithmes et structures de données
Algorithmes: tri, recherche et arbres
BinarySearchTree pourra être réalisée à partir du squelette de code téléchargeable ici.
Plusieurs méthodes permettent de parcourir un arbre binaire de recherche. Néanmoins, pour que le parcours puisse se faire de manière croissante relativement aux étiquettes des différents noeuds, il convient de parcourir l'arbre récursivement en commençant par parcourir le sous-arbre de gauche, puis la racine et finalement le sous-arbre de droite. Plus précisément, en supposant que le contenu de chaque noeud corresponde à l'étiquette du noeud, le parcours de l'arbre ci-dessous donne l'affichage 1, 3, 4, 6, 7, 8, 10, 13, 14.
Arbre binaire de recherche à parcourir
Dans la classe BinarySearchTree, implémentez la méthode print_tree(self) --> None affichant récursivement le contenu de chaque noeud de l'arbre selon l'ordre croissant des étiquettes les identifiant.
|
La recherche dans un arbre binaire d'un noeud ayant une étiquette particulière est un procédé récursif. On commence par examiner la racine. Si l'étiquette de la racine est l'étiquette recherchée, l'algorithme se termine et renvoie la racine. Si l'étiquette recherchée est inférieure, alors elle est dans le sous-arbre de gauche, sur lequel on effectue alors récursivement la recherche. De même, si l'étiquette recherchée est strictement supérieure à l'étiquette de la racine, la recherche continue sur le sous-arbre de droite. Si on atteint une feuille dont l'étiquette n'est pas celle recherchée, on sait alors que cette étiquette n'est pas dans l'arbre.
Recherche du noeud d'étiquette 6
Cette opération requiert un temps en log(n) dans le cas moyen mais en n dans le pire des cas où l'arbre est complètement déséquilibré, c'est-à-dire quand chaque père a un seul fils.
Dans la classe BinarySearchTree, implémentez les méthodes find_recursive(self, node, key) et find_iterative(self, node, key) permettant de rechercher récursivement et itérativement le noeud possédant l'étiquette key à partir du noeud node. La méthode retournera le noeud cherché si celui-ci est trouvé et None sinon.
Implémentez également la méthode search(self, key) permettant de rechercher itérativement le noeud d'étiquette key à partir de la racine de l'arbre binaire de recherche.
|
L'insertion d'un noeud commence par une recherche: on cherche l'étiquette du noeud à insérer. Si le noeud est déjà présent dans l'arbre, il ne faut pas insérer de nouveau noeud mais remplacer son contenu par le nouveau contenu. S'il n'est pas présent dans l'arbre, on ajoute le nouveau noeud comme fils de la feuille sur laquelle on est arrivé en comparant son étiquette à celle de la feuille: si elle est inférieure, le nouveau noeud sera à gauche; sinon, il sera à droite. Ainsi, chaque noeud ajouté sera une feuille.
L'ordre dans lequel l'insertion des noeuds se fait est très important pour la forme finale de l'arbre. Par exemple, si l'on insère les clés [8, 3, 10, 1, 6, 4, 7, 14, 13] dans cet ordre, on obtiendra l'arbre suivant.
Résultat des insertions [8, 3, 10, 1, 6, 4, 7, 14, 13] dans cet ordre
Cette opération requiert un temps en log(n) dans le cas moyen et en n dans le pire des cas.
Dans la classe BinarySearchTree, implémentez la méthode insert(self, key, content) capable d'insérer un nouveau noeud d'étiquette key et de contenu content. La méthode retournera True si un nouveau noeud a été inséré et False si le contenu du noeud d'étiquette key a été modifié.
|
La suppression d'un noeud dans un arbre binaire de recherche nécessite de considérer trois cas:
Suppression d'une feuille
Suppression d'un noeud avec un seul fils
Suppression d'un noeud avec deux fils
Dans tous les cas, cette opération requiert de parcourir l'arbre de la racine jusqu'à une feuille: le temps d'exécution est donc proportionel à la profondeur de l'arbre qui vaut n dans le pire des cas.
Dans la classe BinarySearchTree, implémentez les méthodes suivantes:
replace_node(self, node, new_node) --> None: remplace le noeud node par le nouveau noeud new_node en mettant à jour son parent s'il existe et en tenant compte du fait que new_node peut correspondre à None.remove_node(self, node) --> None: supprime le noeud node de l'arbre en traitant les 3 cas de figures ci-dessus. La méthode recourra au travail réalisé par la méthode replace_node.delete(self, key) --> key deleted or None: supprime le noeud de l'arbre possédant l'étiquette key et retourne cette étiquette si noeud existait et None sinon. La méthode recourra au travail réalisé par la méthode remove_node.|
Le code complet de l'implémentation peut être téléchargé ici. Pour faciliter l'étude du code et le comprendre de manière approfondie, il est possible d'utiliser l'outil en ligne Python Tutor afin de visualiser l'exécution du code lors de l'insertion, de la recherche et de la suppression d'un élément ainsi que de l'affichage du contenu de l'arbre. Cet outil permet d'exécuter le code pas à pas pour visualiser son exécution.
