Aller au contenu
Compétences évaluées
Concevoir des solutions algorithmiques
Traduire un algorithme dans un langage de programmation

Tous les TP seront notés (barème indicatif).

  • Tout TP non rendu avant la fin de la séance sera noté zéro.
  • Veuillez mettre clairement vos noms sur votre code source ou noms de fichiers.

Arbres binaires de recherche

Recherche dichotomique (10 points)

Lorsque l'on a un tableau trié et que l'on cherche une valeur, on peut utiliser la recherche dichotomique pour trouver efficacement (c'est à dire rapidement) cet élément.

Pour cela on va découper le tabeau en deux à chaque fois et regarder si la valeur recherchée est inférieure ou supérieure à la valeur au milieu du tableau.

Dans le code ci-dessous on renvoie True si la valeur recherchée est bien dans le tableau et False sinon.

Par exemple si on cherche la valeur 4 avec le tableau suivant :

[1, 2, 3, 4]

On rappelle que // est l'opérateur de la division entière.

L'exécution de la fonction sera :

Etape 1
-------

bas = 0
haut = 3
milieu = (0 + 3) // 2 = 1

- Le milieu est positionné à la valeur 2, car cela correspond à l'indice 1 du tableau.
- 2 est plus petit que 4, donc on sait que 4 se trouve à droite du tableau.

Etape 2
-------

bas = milieu + 1 = 1 + 1 = 2
haut = 3
milieu = (2 + 3) // 2 = 2

- Le milieu est positionné à la valeur 3, car cela correspond à l'indice 2 du tableau.
- 3 est plus petit que 4, donc on sait que 4 se trouve à droite du tableau.

Etape 3
-------

bas = milieu + 1 = 2 + 1 = 3
haut = 3
milieu = (3 + 3) // 2 = 3

- Le milieu  est positionné à la valeur 4, la fonction retourne True.
  • Complétez le code suivant :
def recherche_dichotomique(tableau, valeur_recherchee, bas, haut):
    if bas > haut:
        return False
    else:
        milieu = #COMPLETER_ICI#
        if valeur_recherchee == tableau[milieu]:
            return #COMPLETER_ICI#
        # La valeur recherchée est à droite
        elif valeur_recherchee > tableau[milieu]:
            return recherche_dichotomique(tableau, #COMPLETER_ICI#, #COMPLETER_ICI# + 1, haut)
        else:
            # La valeur recherchée est à gauche
            return recherche_dichotomique(tableau, #COMPLETER_ICI# , #COMPLETER_ICI#, milieu - 1)

tableau = [3, 4, 5, 6, 7, 18, 19]
valeur_recherchee = 19

result = recherche_dichotomique(tableau, valeur_recherchee, 0, len(array) - 1)

Exercice 2 (10 points)

Soit la classe suivante qui nous sert à représenter un noeud d'un arbre binaire de recherche.

class Noeud():
    def __init__(self, v):
        self.#COMPLETER# = None
        self.ad = None
        self.v = v

    def insere(self, v):
        n = self
        est_insere = #Completer#
        while not est_insere :
            if v == n.v:
                est_insere = True
            elif v < n.v:
                if n.ag != None:
                    n = n.ag
                else:
                    n.ag = Noeud(v)
                    est_insere = #Completer#
            else:
                if n.ad != None:
                    n = n.ad
                else:
                    n.ad = Noeud(v)
                    est_insere = #Completer#

    def #COMPLETER#(self, vals):
        for v in #COMPLETER#:
            self.insere(v)

    def recherche(#COMPLETER#):
        if v == self.v:
            return #COMPLETER#

        elif #COMPLETER:
            if self.ag is not None:
                return self.#COMPLETER#.recherche(v)
            else:
                return False

        elif #COMPLETER:
            if self.ad is not None:
                return self.#COMPLETER#.recherche(v)
            else:
                return False

racine = Noeud(18)
racine.insere_toutes_valeurs([12, 13, 15])
  • Complétez la méthode recherche(self, v) qui prend en argument un entier v et renvoie la valeur True si cet entier est une étiquette de l’arbre (c'est à dire si la valeur appartient à l'arbre), False sinon.

  • Ajouter deux assertions qui testent que la fonction recherche renvoie bien le bon résultat (cas où la valeur appartient à l'arbre et cas où la valeur n'appartient pas à l'arbre).

    image