Insertion et valeurs supérieures dans un ABR

D'après 2022, Métropole, J2, Ex. 1

Dans cet exercice, la taille d'un arbre est le nombre de nœuds qu'il contient. Sa hauteur est le nombre de nœuds du plus long chemin qui joint le nœud racine à l'une des feuilles (nœuds sans sous-arbres). On convient que la hauteur d'un arbre ne contenant qu'un nœud vaut 1 et la hauteur de l'arbre vide vaut 0.

1.a. On considère l'arbre binaire représenté ci-dessous :

graph
N0((15)) --- N1((13))
N0 --- N2((21))
N1 --- N3((11))
N1 --- N4((14))
N2 --- N5((18))
N2 --- N6((27))
N5 --- N7(( ))
linkStyle 6 stroke-width:0px;
style N7 opacity:0;
N5 --- N8((20))

1.a. Donner la taille de cet arbre.

Réponse

La taille vaut 8.

1.b. Donner la hauteur de cet arbre.

Réponse

La hauteur vaut 4.

1.c. Représenter sur la copie le sous-arbre à droite du nœud de valeur 15.

Réponse 
graph
N2((21)) --- N5((18))
N2 --- N6((27))
N5 --- N7(( ))
linkStyle 2 stroke-width:0px;
style N7 opacity:0;
N5 --- N8((20))

1.d. Justifier que l'arbre de la figure 1 est un arbre binaire de recherche.

Réponse

Un arbre binaire de recherche est un arbre tel que, pour tout nœud \(n\), les valeurs associées à tous les nœuds du sous-arbre à gauche sont inférieures à la valeur de \(n\), et les valeurs associées à tous les nœuds du sous-arbre à droite sont supérieures à la valeur associée à \(n\).

On vérifie donc :

  • 15 > 13
  • 13 > 11
  • 13 < 14
  • 15 < 21
  • 21 > 18
  • 18 < 20
  • 21 < 27

Cette propriété étant récursive, on doit aussi vérifier que l'on a :

  • 15 > 14
  • 15 < 18
  • 15 < 17
  • 21 > 20

Remarque : Il est inutile de vérifier que l'on a 15 > 11 car on a vérifié 15 > 13 et 13 > 11. De la même façon, la vérification 15 < 27 est inutile.

1.e. On insère la valeur 17 dans l'arbre de la figure 1 de telle sorte que 17 soit une nouvelle feuille de l'arbre et que le nouvel arbre obtenu soit encore un arbre binaire de recherche. Représenter sur la copie ce nouvel arbre.

Réponse 
graph
N0((15)) --- N1((13))
N0 --- N2((21))
N1 --- N3((11))
N1 --- N4((14))
N2 --- N5((18))
N2 --- N6((27))
N5 --- N7((17))
N5 --- N8((20))

2. On considère l'arbre la classe Noeud définie de la façon suivante en Python :

🐍 Script Python
1
2
3
4
5
class Noeud:
    def __init__(self, gauche, valeur, droite):
        self.gauche = gauche
        self.valeur = valeur
        self.droite = droite

2.a. Parmi les trois instructions (A), (B) et (C) suivantes, écrire sur la copie la lettre correspondant à celle qui construit et stocke dans la variable abr l'arbre représenté ci-dessous.

graph
N0((15)) --- N1((13))
N0 --- N2((21))
  • (A) abr = Noeud(Noeud(Noeud(None, 13, None), 15, None), 21, None)
  • (B) abr = Noeud(None, 13, Noeud(Noeud(None, 15, None), 21, None))
  • (C) abr = Noeud(Noeud(None, 13, None), 15, Noeud(None, 21, None))
Réponse

On utilise l'instruction (C) :

🐍 Script Python
abr = Noeud(
        Noeud(None, 13, None),
        15,
        Noeud(None, 21, None)
)

2.b. Recopier et compléter la ligne 7 du code de la fonction inserer ci-dessous qui prend en paramètres une valeur v et un arbre binaire de recherche abr et qui renvoie l'arbre obtenu suite à l'insertion de la valeur v dans l'arbre abr. Les lignes 8 et 9 permettent de ne pas insérer la valeur v si celle-ci est déjà présente dans abr.

🐍 Script Python
1
2
3
4
5
6
7
8
9
def inserer(v, abr):
    if abr is None:
        return Noeud(None, v, None)
    if v > abr.valeur:
        return Noeud(abr.gauche, abr.valeur, ins(v, abr.droite))
    elif v < abr.valeur:
        return ...
    else:
        return abr
Réponse

On propose :

🐍 Script Python
1
2
3
4
5
6
7
8
9
def inserer(v, abr):
    if abr is None:
        return Noeud(None, v, None)
    if v > abr.valeur:
        return Noeud(abr.gauche, abr.valeur, ins(v, abr.droite))
    elif v < abr.valeur:
        return Noeud(ins(v, abr.gauche), abr.valeur, abr.droite)
    else:
        return abr

3. La fonction nb_sup prend en paramètres une valeur v et un arbre binaire de recherche abr et renvoie le nombre de valeurs supérieures ou égales à la valeur v dans l'arbre abr.

Le code de cette fonction nb_sup est donné ci-dessous :

🐍 Script Python
1
2
3
4
5
6
7
def nb_sup(v, abr):
    if abr is None:
        return 0
    elif abr.valeur >= v:
        return 1+nb_sup(v, abr.gauche)+nb_sup(v, abr.droite)
    else:
        return nb_sup(v, abr.gauche)+nb_sup(v, abr.droite)

3.a. On exécute l'instruction nb_sup(16, abr) dans laquelle abr est l'arbre initial de la question 1.. Déterminer le nombre d'appels à la fonction nb_sup.

Réponse

La fonction va faire autant d'appel que l'arbre compte de sous-arbres y compris les sous-arbres vides. En comptant l'appel initial cela fait donc 17 appels.

3.b. L'arbre passé en paramètre étant un arbre binaire de recherche, on peut améliorer la fonction nb_sup précédente afin de réduire ce nombre d'appels.

Écrire sur la copie le code modifié de cette fonction.

Réponse

Dans la mesure où l'on souhaite compter les valeurs supérieures, il est inutile d'explorer le sous-arbre à gauche si la valeur d'un nœud est inférieure à la valeur passée en argument.

On peut donc faire :

🐍 Script Python
def nb_sup(v, abr):
    if abr is None:
        return 0
    elif abr.valeur >= v:
        return nb_sup(v, abr.gauche) + 1 + nb_sup(v, abr.droite)
    else:
        return nb_sup(v, abr.droite)