Ce "TD-TP" est, comme son nom l'indique, constitué une partie TD à faire sur papier (il est conseillé de faire aussi l'exercice 7 sur machine) & d'une partie TP à faire sur machine.
Il n'est pas nécessaire de faire tout le TD avant d'attaquer le TP, néanmoins, avant de programmer un algorithme, il faut l'écrire à la main.
Donnez des algorithmes (avec leur complexité) qui calculent:
Indication.
On pourra se restreindre aux arbres binaires
Dessinez un arbre de recherche.
Indication.
Que donnent les trois parcours classiques (En-ordre, Pré-Ordre, Post-Ordre) sur un arbre de recherche ?
Indication
Donnez des algorithmes (avec leurs complexités) qui :
Donnez un algorithme qui, à partir d'une liste de nombres, crée un arbre de recherche (Indication). Quel est cet algorithme (Indication)?
Quel est le lien entre recherche dichotomique & arbres de recherche ?
Écrivez la recherche dichotomique (de préférence de manière itérative). Attention, la recherche dichotomique est un algorithme très simple mais sur lequel on fait beaucoup d'erreurs — Testez bien votre programme.
Il existe deux versions de la recherche dichotomique : soit on arrête l'algorithme dès qu'on a trouvé la valeur, soit on va systématiquement jusqu'à avoir un (sous-)tableau de taille 1 & on vérifie s'il contient la valeur recherchée. Quelle est la version la plus efficace ? Indication
Avantages & inconvénients des arbres de recherche par rapport aux tableaux triés ? Réponse
Un arbre binaire est ici défini comme suit :
None
Un arbre binaire de recherche respecte de plus la contrainte suivante:
Nous implémentons dans ce TP un arbre binaire de recherche.
Ouvrez l'éditeur Pycharm et créez un nouveau projet.
Dans ce projet, créez un fichier python arbreBinaireRecherche.py
et un fichier de test testeABR.py
L'accès aux valeurs de l'arbre se fait à partir la racine. Pour commencer, nous créons 3 étiquettes:
INDEX = 0 GAUCHE = 1 DROIT = 2
init_arbre
qui crée un arbre de recherche vide.feuille
qui prend en argument une valeur et retourne une feuilleL'insertion de valeurs se fait généralement de manière récursive, comme suit:
algo : insérer_rec données : * racine * val début: si racine est nul: retourner feuille(val) sinon: si val < racine[INDEX]: racine[GAUCHE] <-- insérer_rec(racine[GAUCHE], val) sinon: racine[DROIT] <-- insérer_rec(racine[DROIT], val) retourner racine
insérer_rec
dans arbreRecherche.py
Écrivez et testez une fonction qui affiche les valeurs de l'arbre selon le parcours "en ordre".
recherche_rec
qui prend en argument une valeur et retourne True
si la valeur est présente dans l'arbre et False
si elle est absente. cherche_max
qui retourne le plus grand élément d'un arbrecherche_max
pour écrire une fonction de suppression récursive supprime_rec
qui prend en argument une valeur et supprime la valeur si celle-ci est présente dans l'arbre et ne change rien sinon. Pour bien comprendre l'effet de la suppression, essayez de produire un affichage un peu plus joli pour l'arbre, par exemple :
| | | |41 | | |32-| | |27-| | | |24 |23-| | | |16 | |14-| | | |12 10-| | | |8 | |7--| | | |6--| | | | |5 |3--| | |2--| | | |1