Chapitre 6. Arbres

• L’abre vide est représenté par un tableau vide : [] ;
• Un arbre non vide est représenté par un tableau de trois cases [v, g, d] où :
  • v désigne la valeur de la racine de l’arbre (type int) ;
  • g désigne son sous arbre de gauche (type list, qui peut être l’arbre vide) ;
  • d désigne son sous arbre de droite (type list, qui peut être l’arbre vide) ;

Exemples. On déclare les arbres suivants :

arb1 = [5, [], []]
arb2 = [
    5,
    [4, [], []],
    [3, [], []]
]

%%{init: {'graph' : {'curve' : 'linear'}}}%%
flowchart TB
    n5((&nbsp5  )) --- n4((&nbsp4  )) & n3((&nbsp3  ))
    n4 --- n01(( )) & n02(( ))
    n3 --- n03(( )) & n04(( ))

• L’arbre vide est représenté par le littéral None (type NoneType);
• Un arbre non vide est représenté par la classe ArbreBin dont les attributs sont :
  • self.valeur : valeur du nœud racine
  • self.gauche : sous-arbre binaire de gauche (type ArbreBin ou NoneType)
  • self.droite : sous-arbre binaire de droite (type ArbreBin ou NoneType)

Voici le code minimal de la classe avec son constructeur :

1
2
3
4
5
6

class ArbreBin:

    def __init__(self, v, g=None, d=None):
        self.valeur = v
        self.gauche = g
        self.droite = d

Remarque. L’arbre vide représenté par None n’appartient par à la classe ArbreBin. Il faudra donc traiter le cas des arbres vides à part lorsque l’on écrira les métodes de la classe ArbreBin.

Exemples. On déclare les arbres suivants :

arb1 = ArbreBin(5)
arb2 = ArbreBin(
    5,
    ArbreBin(4),
    ArbreBin(3)
)
arb3 = ArbreBin(
    5,
    ArbreBin(4, None, None),
    ArbreBin(3, None, None)
)

%%{init: {'graph' : {'curve' : 'linear'}}}%%
flowchart TB
    n5((&nbsp5  )) --- n4((&nbsp4  )) & n3((&nbsp3  ))
    n4 --- n01(( )) & n02(( ))
    n3 --- n03(( )) & n04(( ))

Les trois parcours en profondeurs sont des algorithmes récursifs qui ne se distinguent que par la position du traitement de la racine de l’arbre courant par rapport aux appels récursifs qui s’appliquent à ses sous-arbres.

fonction parcours(arb):
    Si arb n'est pas l'arbre vide:
        Traiter la racine de arb
        parcours(sous-arbre de gauche de arb)
        parcours(sous-arbre de droite de arb)

fonction parcours(arb):
    Si arb n'est pas l'arbre vide:
        parcours(sous-arbre de gauche de arb)
        Traiter la racine de arb
        parcours(sous-arbre de droite de arb)

fonction parcours(arb):
    Si arb n'est pas l'arbre vide:
        parcours(sous-arbre de gauche de arb)
        parcours(sous-arbre de droite de arb)
        Traiter la racine de arb

Le parcours en largeur n’est pas un algorithme récursif mais il nécessite l’utilisation d’une file.

fonction parcours_largeur(arb):
    Creer une file f puis y enfiler arb
    Tant que la file f n'est pas vide:
        Défiler f et récupérer sa tête notée a
        Si a n'est pas l'arbre vide:
            Traiter la racine de a
            Enfiler dans f les sous-arbres de a

Au lieu d’écrire de simples fonctions de parcours récursives, comme dans la version 1, on ajoute directement des méthodes de parcours à la classe ArbreBin.

Cela va introduitre une difficulté supplémentaire : il faut traiter le cas de l’arbre vide (représenté par None) de manière spécifique. En effet, il n’est pas possible de passer en paramètre des méthodes de la classe ArbreBin l’arbre vide None car le littéral None n’appartient pas à cette classe.

On s’assure donc qu’un sous-arbres n’est pas l’arbre vide avant de lancer un appel récursif.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

class ArbreBin:

    def __init__(self, v, g=None, d=None):
        self.valeur = v
        self.gauche = g
        self.droite = d

    def prefixe(self):
        print(self.valeur)
        if self.gauche != None:
            self.gauche.prefixe()
        if self.droite != None:
            self.droite.prefixe()

    def infixe(self):
        if self.gauche != None:
            self.gauche.infixe()
        print(self.valeur)
        if self.droite != None:
            self.droite.infixe()

    def suffixe(self):
        if self.gauche != None:
            self.gauche.suffixe()
        if self.droite != None:
            self.droite.suffixe()
        print(self.valeur)

    def parcours_largeur(self):
        f = File()
        f.enfiler(self)
        while not f.est_vide():
            a = f.defiler()
            if a != None:
                print(a.valeur)
                f.enfiler(a.gauche)
                f.enfiler(a.droite)

Cet exercice porte sur les arbres binaires et les arbres binaires de recherche.

Dans cet exercice, on utilisera la convention suivante : la hauteur d’un arbre binaire ne comportant qu’un nœud est 1.

1. Déterminer la taille et la hauteur de l’arbre binaire suivant.

   flowchart TB
       A([A]) --- B([B]) & E([E]);
       B --- C([C]) & D([D]);
       E --- F([F]);
       E ~~~ F2([F2]):::hidden;
       D --- G([G]);
       D ~~~ G2([G2]):::hidden;
       F --- H([H]) & I([I]);
       classDef hidden display: none;
   

   Réponse

   • Cet arbre a pour taille 9.

     Justification non exigée ici.

     En effet, cet arbre possède un total de 9 nœuds.

   • Cet arbre a pour hauteur 4.

     Justification non exigée ici.

     Le chemin le plus long de cet arbre est A—B—D—G (ou A—E—F—H ou A—E—F—I). Ce chemin est composé de 4 nœuds et 3 arêtes. Dans le contexte de cet exercice, cet arbre a donc pour hauteur 4. En effet, d’après l’énoncé, on utilise la convention « la hauteur d’un arbre binaire ne comportant qu’un nœud est 1 ». Avec cette convention, la hauteur d’un arbre est le nombre de nœuds de son chemin le plus long.

2. On décide de numéroter en binaire les nœuds d’un arbre binaire de la façon suivante :

   • la racine correspond à 1:
   • la numérotation pour un fils gauche s’obtient en ajoutant le chiffre 0 à droite au numéro de son père ;
   • la numérotation pour un fils droit s’obtient en ajoutant le chiffre 1 à droite au numéro de son père ;

   Par exemple, dans l’arbre ci-dessous, on a utilisé ce procédé pour numéroter les nœuds A, B, C, E et F.

   flowchart TB
       A([A:1]) --- B([B:10]) & E([E:11]);
       B --- C([C:100]) & D([D:?]);
       E --- F([F:110]);
       E ~~~ F2([F2]):::hidden;
       D --- G([G:?]);
       D ~~~ G2([G2]):::hidden;
       F --- H([H:?]) & I([I:?]);
       classDef hidden display: none;
   

   1. Dans l’exemple précédent, quel est le numéro en binaire associé au nœud G ?

      Réponse

      Le nœud G est associé au numéro 1010.

      Justification non exigée ici.

      Sur l’arbre fourni comme exemple à la question 2., on complète le chemin menant au nœud G.

      flowchart TB
          A([A:1]) --- B([B:10]) & E([E:11]);
          B --- C([C:100]) & D([D:101]):::emphase;
          E --- F([F:110]);
          E ~~~ F2([F2]):::hidden;
          D --- G([G:1010]):::emphase;
          D ~~~ G2([G2]):::hidden;
          F --- H([H:?]) & I([I:?]);
          classDef emphase stroke-width: 3px;
          classDef hidden display: none;
      

   2. Quel est le nœud dont le numéro en binaire vaut 13 en décimal ?

      Réponse

      $$\begin{align*} 13 &= 8 + 4 + 1 \\ &= 2^3 + 2^2 + 2^0 \\ &= 1101|_2 \end{align*}$$

      Le nœud dont le numéro en binaire vaut 13 est donc I.

      Justification non exigée ici.

      Sur l’arbre fourni comme exemple à la question 2., on complète les nœuds I et H.

      flowchart TB
          A([A:1]) --- B([B:10]) & E([E:11]);
          B --- C([C:100]) & D([D:101]);
          E --- F([F:110]);
          E ~~~ F2([F2]):::hidden;
          D --- G([G:1010]);
          D ~~~ G2([G2]):::hidden;
          F --- H([H:1100]):::emphase & I([I:1101]):::emphase;
          classDef emphase stroke-width: 3px;
          classDef hidden display: none;
      

   3. En notant $h$ la hauteur de l’arbre, sur combien de bits seront numérotés les nœuds les plus en bas ?

      Réponse

      L’arbre donné en exemple à la question 2. a pour hauteur 4. Ses nœuds les plus en bas (G, H et I) sont numérotés sur 4 bits. De même, pour un arbre de hauteur $h$, ses nœuds les plus en bas seront numérotés sur $h$ bits.

   4. Justifier que pour tout arbre de hauteur $h$ et de taille $n \geq 2$, on a : $$\begin{align*} h \leq n \leq 2^h - 1 \end{align*}$$

      Réponse

      Pour une hauteur $h$, un arbre ayant le moins de nœuds se résume à un chemin de $n = h$ nœuds où chaque nœud possède un seul fils sauf l’unique feuille. On donne ci-dessous un exemple pour $h = 4$.

      flowchart TB
          A([A]) --- B([B]);
          A ~~~ B2([B2]):::hidden;
          B ~~~ C0([C0]):::hidden;
          B --- C([C]);
          C ~~~ D0([D0]):::hidden;
          C --- D([D]);
          classDef emphase stroke-width: 3px;
          classDef hidden display: none;
      

      Pour une hauteur $h$, un arbre binaire ayant le plus de nœuds est un arbre binaire complet c’est-à-dire un arbre où chaque nœud possède exactement deux nœuds fils sauf les feuilles qui ont toute pour profondeur de $h$ (avec pour convention une profondeur de 1 pour la racine d’un arbre). Cet arbre possède $n = 2^h - 1$ nœuds. On donne ci-dessous un exemple pour $h = 4$.

      flowchart TB
          A([A]) --- B([B]) & C([C]);
          B --- D([D]) & E([E]);
          C --- F([F]) & G([G]);
          D --- H([H]) & I([I]);
          E --- J([J]) & K([K]);
          F --- L([L]) & M([M]);
          G --- N([N]) & O([O]);
          classDef emphase stroke-width: 3px;
          classDef hidden display: none;
      

      Cet arbre a bien un taille de : $$\begin{align*} n &= 2^4 - 1 \\ &= 16 - 1 \\ &= 15 \end{align*}$$

      On en déduit l’encadrement de l’énoncé. Un arbre binaire de hauteur $h$ a bien une taille $n$ comprise entre $h$ (minimum) et $2^h - 1$ (maximum). Pour $h = 4$, on a donc $4 \leq n \leq 15$.

3. Un arbre binaire est dit complet si tous les niveaux de l’arbre sont remplis.

   flowchart TB
       A([A]) --- B([B]) & C([C]);
       B --- D([D]) & E([E]);
       C --- F([F]) & G([G]);
       D --- H([H]) & I([I]);
       E --- J([J]) & K([K]);
       F --- L([L]) & M([M]);
       G --- N([N]) & O([O]);
       classDef emphase stroke-width: 3px;
       classDef hidden display: none;
   

   Abre binaire complet

   On décide de représenter un arbre binaire complet par un tableau de taille $n + 1$, où $n$ est la taille de l’arbre, de la façon suivante :

   • la racine a pour indice 1 ;
   • le fils de gauche du nœud d’indice $i$ a pour indice $2 \times i$ ;
   • le fils droit du nœud d’indice $i$ a pour indice $2 \times i + 1$ ;
   • on place la taille $n$ de l’arbre dans la case d’indice $0$.

   1. Déterminer le tableau qui représente l’arbre binaire complet de l’exemple précédent.

      Réponse

      0	1	2	3	4	5	6	7	8	9	10	11	12	13	15	16
      15	A	B	C	D	E	F	G	H	I	J	K	L	M	N	O

      Justification non exigée ici.

      • L’arbre binaire précédent a pour taille $n = 15$ (il possède 15 nœuds au total). On place donc 15 dans la case d’indice 0 du tableau.
      • L’arbre binaire précédent a pour racine A. On place donc A dans la case de rang 1 du tableau.
      • Le nœud A est placé dans la case $i = 1$ du tableau.
        • Son fils gauche, le nœud B, a pour rang dans le tableau : $$\begin{align*} 2 \times i &= 2 \times 1 \\ &= 2 \end{align*}$$ On place donc B dans la case d’indice 2 du tableau.
        • Son fils droit, le nœud C, a pour rang dans le tableau : $$\begin{align*} 2 \times i + 1 &= 2 \times 1 + 1\\ &= 3 \end{align*}$$ On place donc C dans la case d’indice 3 du tableau.
      • Le nœud B est placé dans la case $i = 2$ du tableau.
        • Son fils gauche, le nœud D, a pour rang dans le tableau : $$\begin{align*} 2 \times i &= 2 \times 2 \\ &= 4 \end{align*}$$ On place donc D dans la case d’indice 4 du tableau.
        • Son fils droit, le nœud E, a pour rang dans le tableau : $$\begin{align*} 2 \times i + 1 &= 2 \times 2 + 1\\ &= 5 \end{align*}$$ On place donc E dans la case d’indice 5 du tableau.

      On ajoute ensuite le reste des nœuds de l’arbre dans le tableau selon le même principe.

   2. On considère le père du nœud d’indice $i$ avec $i \ge 2$. Quel est son indice dans le tableau ?

      Réponse

      Le père d’un nœud d’indice $i$ a pour indice le quotient de la division euclidienne de $i$ par 2. On peut noter cette indice comme la partie entière de la division de $i$ par 2 :

      $$\begin{align*} \left\lfloor \frac{i}{2} \right\rfloor \end{align*}$$

      Remarques.

      • Ce résultat s’obtient en Python avec l’opérateur division entière // : i // 2.

      • Par exemple, le nœud F a pour indice $i = 6$ dans le tableau. Son père, le nœud C, a pour indice 3 dans le tableau. On peut retrouver ce résultat par le calcul :

      $$\begin{align*} \left\lfloor \frac{i}{2} \right\rfloor &= \left\lfloor \frac{6}{2} \right\rfloor \\ &= \left\lfloor 3 \right\rfloor \\ &= 3 \end{align*}$$

      • Par exemple, le nœud G a pour indice $i = 7$ dans le tableau. Son père, le nœud C, a pour indice 3 dans le tableau. On peut retrouver ce résultat par le calcul :

      $$\begin{align*} \left\lfloor \frac{i}{2} \right\rfloor &= \left\lfloor \frac{7}{2} \right\rfloor \\ &= \left\lfloor 3{,}5 \right\rfloor \\ &= 3 \end{align*}$$

4. On se place dans le cas particulier d’un arbre binaire de recherche complet où les nœuds contiennent des entiers et pour lequel la valeur de chaque nœud est supérieure à celles des nœuds de son fils de gauche, et inférieure à celles des nœuds de son fils droit.

   Écrire une fonction recherche ayant pour paramètres un arbre abr et une valeur val. Cette fonction renvoie True si val est dans l’arbre et False sinon. L’arbre sera représenté par un tableau comme dans la question précédente.

   Réponse

   On écrit une fonction de recherche binaire.

   1 2 3 4 5 6 7 8 9 10

   def recherche(abr, val): i = 1 #(1)! while i < len(abr): #(2)! if val == abr[i]: return True #(3)! elif val < abr[i]: i = 2 * i #(4)! else: # val > abr[i] i = 2 * i + 1 #(5)! return False #(6)!

   1. La racine est le premier nœud visité à l’indice $i = 1$ dans le tableau abr.

   2. Tant que l’on a pas encore atteint la fin du tableau abr. La condition i < abr[0] convenait également puisque la taille de l’arbre est placée dans la case d’indice 0 du tableau.

   3. Cet algorithme est en temps non constant : le parcours du tableau s’arrête dès que la valeur est trouvée avec le renvoi de True qui met un terme à l’exécution de l’appel.

   4. Si la valeur recherchée est strictement inférieure à la valeur du nœud courant, il faut continuer la recherche dans le nœud fils gauche du nœud courant. L’indice du nœud courant est i. L’indice de son nœud fils gauche est 2 * i.

   5. Si la valeur recherchée est strictement supérieure à la valeur du nœud courant, il faut continuer la recherche dans le nœud fils droit du nœud courant. L’indice du nœud courant est i. L’indice de son nœud fils droit est 2*i + 1.

   6. Cet algorithme est en temps non constant : si la boucle while s’est terminée, cela signifie que l’arbre binaire de recherche a été parcouru jusqu’à une feuille sans trouver la valeur. Cela signifie que la valeur est absente de l’arbre.

   Remarque 1

   Cette fonction n’est pas récursive mais itérative. On voit ici l’intérêt de représenter un arbre binaire par un tableau. Cela permet de combiner les avantages d’un ABR et d’un tableau :

   • recherche rapide pour l’ABR ;
   • algorithmes itératifs pour un tableau.

   Par contre, dans le contexte de l’exercice, les ABR sont complets, il n’est donc question que de recherche et non d’insertion.

   Remarque 2

   L’énoncé était un peu ambigü. En effet, une simple recherche linéaire aurait pu être acceptée. On en donne ci-dessous deux implémentations :

   • en temps non-constant

     1 2 3 4 5

     def recherche(abr, val): for elt in abr: if val == elt: return True return False

   • en temps constant

     1 2 3 4 5 6

     def recherche(abr, val): res = False for elt in abr: if val == elt: res = True return res

   Néanmoins, l’efficacité de la recherche binaire dans un ABR complet est bien supérieure à la recherche linéaire. On pouvait donc supposer que la recherche linéaire n’était pas la réponse attendue.

   • Pour la recherche linéaire, le nombre de comparaisons (l’étape déterminante dans cet algorithme) est égale dans le pire des cas au nombre de nœuds de l’arbre c’est-à-dire à sa taille $n$. On parle de complexité en $\mathcal{O}(n)$.

   • Par contre, la recherche binaire ne passe pas en revue tous les nœuds mais parcourt un chemin de la racine à une feuille. Dans le pire des cas, ce chemin possède un nombre de nœud égal à la hauteur de l’ABR. La hauteur d’un ABR complet est églale à $\log_2(n + 1)$. L’exemple d’ABR complet donné à la question 3. a pour taille $n = 15$. Sa hauteur $h$ est donc : $$\begin{align*} h &= \log_2(n + 1) \\ &= \log_2(15 + 1) \\ &= \log_2(16) \\ &= \log_2(2^4) \\ &= 4 \end{align*}$$ Le nombre de comparaisons est donc dans le pire des cas égal à $\log_2(n + 1)$. On parle de complexité en $\mathcal{O}(\log_2(n))$.

   On peut alors comparer le nombre d’étapes dans le pire des cas pour les deux algorithmes de recherche en comparant la taille et la hauteur d’ABR complets. On donne ci-dessous les comparaisons pour trois tailles d’ABR complets mettant clairement en évidence l’intérêt de la recherche binaire.

   	Nombre d’étapes de la recherche…
   Taille de l’ABR	…linéaire (taille $n$ de l’ABR)	…binaire (hauteur $\log_2(n + 1)$ de l’ABR)
   15	15	4
   255	255	8
   1023	1023	10

Cet exercice porte sur les arbres binaires et leurs algorithmes associés.

La fédération de badmington souhaite gérer des compétitions à l’aide d’un logiciel. Pour ce faire, une structure Arbre de compétition a été définie récursivement de la façon suivante : un arbre de compétition est :

• soit l’arbre vide, noté $\varnothing$,

• soit un triplé composé :

  • d’une chaîne de caractères appelée valeur,
  • d’un arbre de compétition appelé sous-arbre gauche et
  • d’un arbre de compétition appelé sous-arbre droit.

On représente un arbre de compétition de la façon suivante :

flowchart TB
    K1('Kamel'):::textOnly --- K2('Kamel'):::textOnly & C2('Carine'):::textOnly
    K2 --- J3('Joris'):::textOnly & K3('Kamel'):::textOnly
    C2 --- C3('Carine'):::textOnly & A3('Abdou'):::textOnly
    J3 --- V41("∅"):::vide & V42("∅"):::vide
    K3 --- V43("∅"):::vide & V44("∅"):::vide
    C3 --- V45("∅"):::vide & V46("∅"):::vide
    A3 --- V47("∅"):::vide & V48("∅"):::vide
    classDef vide fill:#ffffff00, stroke-width:0px, font-size:x-large
    classDef textOnly fill:#ffffff00, stroke-width:0px, font-family:monospace

Pour alléger la représentation d’un arbre de compétition, on ne notera pas les arbres vides, l’arbre précédent sera donc représenté par l’arbre arb1 suivant :

flowchart TB
    K1('Kamel'):::textOnly --- K2('Kamel'):::textOnly & C2('Carine'):::textOnly
    K2 --- J3('Joris'):::textOnly & K3('Kamel'):::textOnly
    C2 --- C3('Carine'):::textOnly & A3('Abdou'):::textOnly
    classDef vide fill:#ffffff00, stroke-width:0px, font-size:x-large
    classDef textOnly fill:#ffffff00, stroke-width:0px, font-family:monospace

Cet arbre se lit de la façon suivante :

• 4 participants se sont affrontés : Joris, Kamel, Carine et Abdou. Leurs noms apparaissent en bas de l’arbre, ce sont les valeurs des feuilles de l’arbre.
• Au premier tour, Kamel a battu Joris et Carine a battu abdou.
• En finale, Kamel a battu Carine, il est donc vainqueur de la compéltition.

Pour s’assurer ue chaque finaliste it joué le même nombre de matchs, un arbre de compétition a toutes ces feuilles à la même hauteur.

On suppose que l’on dispose des quatre fonctions suivantes qui ont été préalablement implémentées en Python. On ne précise pas le détail de leur implémentation.

• La fonction racine prend en paramètre un arbre de compétition arb et renvoie la valeur de la racine de cet arbre.

  Exemple. En reprenant l’exemple d’arbre de compétition présenté ci-dessus, racine(arb1) vaut 'Kamel'.

• La fonction gauche prend en paramètre un arbre de compétition arb et renvoie son sous-arbre gauche.

  Exemple. En reprenant l’exemple d’arbre de compétition présenté ci-dessus, gauche(arb1) vaut l’arbre représenté graphiquement ci-après :

flowchart TB
    K1('Kamel'):::textOnly --- J2('Joris'):::textOnly & K2('Kamel'):::textOnly
    classDef textOnly fill:#ffffff00, stroke-width:0px, font-family:monospace

• La fonction droit prend en paramètre un arbre de compétition arb et renvoie son sous-arbre droit.

  Exemple. En reprenant l’exemple d’arbre de compétition présenté ci-dessus, droit(arb1) vaut l’arbre représenté graphiquement ci-après :

flowchart TB
    C1('Carine'):::textOnly --- C2('Carine'):::textOnly & A2('Abdou'):::textOnly
    classDef textOnly fill:#ffffff00, stroke-width:0px, font-family:monospace

• La fonction est_vide qui prend en argument un arbre de compétition et renvoie True si l’arbre est vide et False sinon.

  Exemple. En reprenant l’exemple d’arbre de compétition présenté ci-dessus, est_vide(arb1) vaut False.

Pour toutes les questions de l’exercice, on suppose que tous les joueurs d’une même compétition ont un prénom différent.

1. On considère l’arbre de compétition $arb2$ suivant :

   flowchart TB
       Le1('Léa'):::textOnly --- Le2('Léa'):::textOnly & Lo2('Louis'):::textOnly
       Le2 --- Le3('Léa'):::textOnly & Th3('Théo'):::textOnly
       Lo2 --- Lo3('Louis'):::textOnly & An3('Anne'):::textOnly
       Le3 --- Ma('Marc'):::textOnly & Le4('Léa'):::textOnly
       Th3 --- Cl4('Claire'):::textOnly & Th4('Théo'):::textOnly
       Lo3 --- Ma4('Marie'):::textOnly & Lo4('Louis'):::textOnly
       An3 --- An4('Anne'):::textOnly & Ke4('Kevin'):::textOnly
       classDef textOnly fill:#ffffff00, stroke-width:0px, font-family:monospace
   

   1. Indiquer la racine de de l’arbre précédent puis donner l’ensemble des valeurs des feuilles de cet arbre.

      Réponse

      La racine de l’arbre $arb2$ a pour valeur 'Léa'. Les feuilles de l’arbre $arb2$ ont pour valeurs respectives : 'Marc', 'Léa', 'Claire', 'Théo', 'Marie', 'Louis', 'Anne' et 'Kevin'.

   2. Proposer une fonction Python vainqueur prenant en paramètre un arbre de compétition arb ayant au moins un joueur. Cette fonction doit renvoyer la chaîne de caractères constituée du nom du vainqueur du tournoi.

      Exemple. vainqueur(arb2) vaut 'Léa'.

      Réponse

      1 2	def vainqueur(arb): return racine(arb)

   3. Proposer une fonction Python finale prnant en paramètre un arbre de compétition ayant au moins deux joueurs. Cette fonction doit renvoyer le tableaux des deux chaînes de caractères qui sont les deux compétitions finalistes.

      Exemple. finale(arb2) vaut ['Léa', 'Louis'].

      Réponse

      1 2 3 4

      def finale(arb): finaliste1 = racine(gauche(arb)) finaliste2 = racine(droit(arb)) return [finaliste1, finaliste2]

2. Les deux questions suivantes sont liées.

   1. Proposer une fonction occurrences prenant en paramètre un arbre de compétition arb et le nom d’un joueur nom et qui renvoie le nombre d’occurrence (d’apparitions) du joueur nom dans l’arbre de compétition arb.

      Exemple. occurences(arb2, 'Anne') vaut 2.

      Réponse

      On utilise une variable d’accumulation :

      1 2 3 4 5 6 7 8

      def occurences(arb, nom): res = 0 if not est_vide(arb): if nom == racine(arb): res += 1 res += occurrences(gauche(arb), nom) res += occurrences(droit(arb), nom) return res

   2. Proposer une fonction a_gagne prenant en paramètres un arbre de compétition arb et le nom d’un joueur nom et qui renvoie le booléen True si le joueur nom a gagné au moins un match dans la compétition représentée par l’arbre de compétition arb.

      Exemple. a_gagne(arb2, 'Louis') vaut True.

      Réponse

      Un joueur ayant gagné au moins un match apparaît au moins 2 fois dans l’arbre : au niveau d’une feuille comme participant en début de compétition, au niveau d’au moins un nœud interne et éventuellment de la racine s’il a gagné au moins un match au cours de la compétition.

      1 2	def a_gagne(arb, nom): return occurrences(arb, nom) > 1

3. On souhaite programmer une fonction Python nombre_matchs qui prend en paramètres un arbre de compétition arb et le nom d’un joueur nom et qui renvoie le nombre de matchs joués par le joueur nom dans la compétition représentée par l’arbre de compétition.

   Exemple. nombre_matchs(arb2, 'Léa') doit valoir 3 et nombre_matchs(arb2, 'Marc') doit valoir 1.

   1. Expliquer pourquoi la définition suivante de la fonction nombre_matchs renvoie un résultat inexact. On pourra pour cela identifier le nœud à l’origine de ce résultat inexact.

      1 2	def nombre_matchs(arb, nom): return occurrences(arb, nom)

      Réponse

      Pour un joueur qui n’a pas gagné la compétition, comme par exemple le joueur Louis dans $arb2$, le nombre de matchs joués par le joueur est égal à son nombre d’occurrences dans l’arbe. Pour Louis ce nombre est 3. En effet, Louis a :

      • gagné un match contre Marie et Anne puis
      • perdu un match contre Léa.

      Par contre, le vainqueur de la compétition voit son nom apparaître dans l’arbre une fois de plus au niveau de la racine de l’arbre. C’est le cas de Léa dans $arb2$ qui a joué 3 matchs mais dont le nom apparaît 4 fois dans l’arbre.

   2. Proposer une version correcte de la définition de la fonction nombre_matchs.

      Réponse

      1 2 3 4 5

      def nombre_matchs(arb, nom): if vainqueur(arb, nom): return occurrences(arb, nom) - 1 else: return occurrences(arb, nom)

4. Recopier et compléter la fonction tab_joueurs qui prend pour argument un arbre de compétition arb et qui renvoie un tableau (type list) contenant es participants à la compétition, chaque nom ne devant figurer qu’une seule fois dans le tableau.

   L’opérateur + à la ligne 8 permet de concaténer deux tableaux.

   Exemple. Si tab1 vaut [4, 6, 2] et tab2 vaut [3, 5, 1], l’expression tab1 + tab2 est évaluée à [4, 6, 2, 3, 5, 1].

   1 2 3 4 5 6 7

   def tab_joueurs(arb): if est_vide(arb): return ... elif ... and ...: return [racine(arb)] else: return ... + tab_joueurs(droit(arb))

   Réponse

   1 2 3 4 5 6 7

   def tab_joueurs(arb): if est_vide(arb): return [] elif est_vide(gauche(arb)) and est_vide(droit(arb)): #(1)! return [racine(arb)] else: return tab_joueurs(gauche(arb)) + tab_joueurs(droit(arb))

   1. L’arbre courant abr est une feuille. En fait cet algorithme n’ajoute que les valeurs des feuilles de l’arbre qui contiennent les noms de tous les joueurs.

Cet exercice porte sur les arbres binaires de recherche et la programmation orientée objet.

On rappelle qu’un arbre binaire est composé de nœuds, chacun des nœuds possédant éventuellement un sous-arbre gauche et éventuellment un sous-arbre droit. Un nœud sans sous arbre est appelé feuille. La taille d’un arbre est son nombre de nœuds ; sa hauteur et le nombre de nœud du plus long chemin qui joint le nœud racine à l’une de ses feuilles. Ainsi, la hauteur d’un arbre réduit à un seul nœud est 1.

Dans un arbre binaire de recherche (ABR), chaque nœud contient une clé, ici un nombre entier, qui est :

• strictement supérieure à toutes les clés des nœuds du sous-arbre gauche ;
• strictement inférieure à toutes les clés des nœuds du sous-arbre droit.

Ainsi les clés d’un ABR sont toutes distinctes.

Un ABR est dit bien construit s’il n’existe pas d’arbre de hauteur inférieure qui pourrait contenir tous ses nœuds.

1. On considère l’ABR ci-dessous.

   flowchart
       12((12)) --- 10((10)) & 15((15))
       10 --- 5([5])
       10 ~~~ N1((N1)):::hidden
       5 --- 4([4]) & 8([8])
       15 ~~~ N2((N2)):::hidden
       15 --- 20((20))
       classDef hidden display: none;
   

   1. Quelle est la taille de l’arbre ci-dessus ?

      Réponse

      Cet arbre possède 7 nœuds donc a pour taille 7.

   2. Quelle est la hauteur de l’arbre ci-dessous ?

      Réponse

      Le chemin le plus long de cet arbre est 12—10—5—4 (ou 12—10—5—8). Ce chemin est composé de 4 nœuds et 3 arêtes. Dans le contexte de cet exercice, cet arbre a donc pour hauteur 4. En effet, d’après l’énoncé, on utilise la convention « la hauteur d’un arbre est le nombre de nœuds de son chemin le plus long ».

2. L’ABR de la question n’est pas bien construit. Proposer un ABR contenant les mêmes clés et dont la hauteur est plus petite que celle de l’arbre initial.

   Réponse

   flowchart
       10((10)) --- 5([5]) & 15((15))
       5 --- 4([4]) & 8([8])
       15 --- 12((12)) & 20((20))
   

3. Les classes Noeud et Arbre ci-dessous permettent de mettre en œuvre en Python la structure d’un ABR. La méthode insere permet d’insérer récursivement une nouvelle clé.

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

   class Noeud: def __init__(self, cle): self.cle = cle self.gauche = None self.droite = None def insere(self, cle): if cle < self.cle: if self.gauche == None: self.gauche = Noeud(cle) else: self.gauche.insere(cle) elif cle > self.cle: if self.droite == None: self.droite = Noeud(cle) else: self.droite.insere(cle) class Arbre: def __init__(self, cle): self.racine = Noeud(cle) def insere(self, cle): self.racine.insere(cle)

   Donner la représentation de l’arbre a déclaré et construit par le programme ci-dessous.

   1 2 3 4 5 6 7

   a = Arbre(10) a.insere(20) a.insere(15) a.insere(12) a.insere(8) a.insere(4) a.insere(5)

   Réponse

   flowchart
       10((10)) --- 5([5]) & 15((15))
       5 --- 4([4]) & 8([8])
       15 --- 12((12)) & 20((20))
   

   Indications

   Il suffit d’insérer les clés dans l’ordre fourni par le programme précédent.

   • Étape 1. Création de l’arbre et ajout de la racine de valeur 10

     flowchart
         10((10))
     

   • Étape 2. Insertion de 20

     flowchart
         10((10)) ~~~ N1((N1)):::hidden
         10 --- 20((20))
         classDef hidden display:none
     

   • Étape 3. Insertion de 15

     flowchart
         10((10)) ~~~ N1((N1)):::hidden
         N1 ~~~ N3((N3)):::hidden
         10 --- 20((20))
         20 --- 15((15))
         20 ~~~ N2((N2)):::hidden
         classDef hidden display:none
     

   • Étape 4. Insertion de 12

     flowchart
         10((10)) ~~~ N1((N1)):::hidden
         N1 ~~~ N3((N3)):::hidden
         10 --- 20((20))
         20 --- 15((15))
         20 ~~~ N2((N2)):::hidden
         15 --- 12((12))
         15 ~~~ N4((N4)):::hidden
         classDef hidden display:none
     

   • Étape 5. Insertion de 8

     flowchart
         10((10)) --- 8([8])
         10 --- 20((20))
         20 --- 15((15))
         20 ~~~ N2((N2)):::hidden
         15 --- 12((12))
         15 ~~~ N4((N4)):::hidden
         classDef hidden display:none
     

   • Étape 6. Insertion de 4

     flowchart
         10((10)) --- 8([8])
         8 --- 4([4])
         8 ~~~ N1((N1)):::hidden
         10 --- 20((20))
         20 --- 15((15))
         20 ~~~ N2((N2)):::hidden
         15 --- 12((12))
         15 ~~~ N4((N4)):::hidden
         classDef hidden display:none
     

   • Étape 7. Insertion de 5

     flowchart
         10((10)) --- 8([8])
         8 --- 4([4])
         4 ~~~ N0((N0)):::hidden
         4 --- 5([5])
         8 ~~~ N1((N1)):::hidden
         10 --- 20((20))
         20 --- 15((15))
         20 ~~~ N2((N2)):::hidden
         15 --- 12((12))
         15 ~~~ N4((N4)):::hidden
         classDef hidden display:none
     

4. Pour calculer la hauteur d’un arbre non vide, on a écrit la méthode ci-dessous dans la classe Noeud.

   1 2 3 4 5 6 7 8 9 10 11 12 13 14

   def hauteur(self): if self.gauche is None and self.droite is None: return 1 elif self.gauche is None: return 1 + self.droite.hauteur() elif self.droite is None: return 1 + self.gauche.hauteur() else: hg = self.gauche.hauteur() hd = self.droite.hauteur() if hg > hd: return 1 + hg else: return 1 + hd

   Écrire la méthode hauteur de la classe Arbre qui renvoie la hauteur de l’arbre.

   Réponse

   Dans la classe Arbre, on ajoute :

   1 2	def hauteur(self): return self.racine.hauteur()

   Remarques.

   • Attention à ne pas oublier le mot-clé return : la méthode hauteur est un accesseur. Au contraire, la méthode insere est un mutateur d’où l’absence du mot-clé return dans la définition de cette dernière méthode.

   • self.racine désigne une instance de la classe Noeud à laquelle on applique la méthode hauteur() de la classe Noeud. Ainsi, la méthode hauteur de la classe Arbre n’est pas récursive :

     • le mot hauteur à la ligne 1 désigne la méthode hauteur de la classe Arbre;
     • le mot hauteur à la ligne 2 désigne la méthode (elle récursive) de la classe Noeud.

     On donne ci-dessous un diagramme d’objet permettant de comprendre la ligne 2. Le diagramme d’objet ci-après correspond à l’ABR arb1 donné à titre d’exemple dessiné ci-dessous :

     flowchart
         12((12)) --- 10((10)) & 15((15))
     

     

5. Écrire les méthodes tailles des classes Noeud et Arbre permettant de calculer la taille d’un arbre.

   Réponse

   Dans la classe Noeud :

   1 2 3 4 5 6 7 8 9 10 11

   def taille(self): if self.gauche is None and self.droit is None: return 1 elif self.gauche is None: return 1 + self.droite.taille(self) elif self.droite is None: return 1 + self.gauche.taille(self) else: tg = self.gauche.taille(self) td = self.droite.taille(self) return 1 + tg + td

   Dans la classe Arbre :

   1 2	def taille(self): return self.racine.taille()

6. On souhaite écrire une méthode bien_construit de la classe Arbre qui renvoie la valeur True si l’arbre est bien construit et False sinon.

   On rappelle que la taille maximale d’un ABR de recherche de hauteur $h$ est $2^h - 1$.

   1. Quelle est la taille minimale, notée $t_{\text{min}}$, d’un ABR bien construit de hauteur $h$ ?

      Réponse

      Un ABR bien construit d’hauteur $h$ a une taille maximale si c’est un arbre binaire complet, c’est-à-dire que tous ses niveaux sont remplis. On a alors $t_{\text{max}} = 2^h - 1$ comme indiqué dans l’énoncé.

      Cependant, un ABR bien construit d’hauteur $h$ n’est pas forcément un arbre binaire complet. En effet, son niveau le plus profond n’est pas forcément rempli : il faut au moins un nœud sur ce dernier niveau. Ainsi, un tel arbre est comme un arbre binaire complet d’hauteur $h - 1$ (et donc de taille $2^{h-1} - 1$) auquel il faut ajouter un minimum de un nœud supplémentaire. Donc :

      $$\begin{align*} t_{\text{min}} &= \left(2^{h-1} - 1\right) + 1 \\ &= 2^{h-1} \end{align*}$$

      Explication visuelle sur un exemple

      Pour cette explication visuelle, on choisit de fixer la hauteur à $h = 4$.

      • Voici un exemple d’ABR bien construit maximisant le nombre de nœuds pour une hauteur de $h = 4$ (c’est tout simplement un arbre binaire complet)

        flowchart
            10((10)) --- 5([5]) & 15((15))
            5 --- 4([4]) & 8([8])
            15 --- 12((12)) & 20((20))
            4 --- 1([1]) & 3([3])
            8 --- 6([6]) & 9([9])
            12 --- 11((11)) & 14((14))
            20 --- 17((17)) & 24((24))
        

        Cet arbre a bien pour hauteur $h = 4$. En comptant ses nœuds on obtient une taille de 15. On retrouve ce résultat avec la formule établie pour $t_{\text{max}}$ :

        $$\begin{align*} t_{\text{max}} &= 2^h - 1 \\ &= 2^4 - 1 \\ &= 16 - 1 \\ &= 15 \end{align*}$$

      • Voici un exemple d’ABR bien construit minimisant le nombre de nœuds pour une hauteur de $h = 4$ :

        flowchart
            8([8]) --- 6([6])
            8 ~~~ N1((N1)):::hidden
            subgraph "Arbre binaire complet (h = 3)"
                10((10)) --- 5([5]) & 15((15))
                5 --- 4([4]) & 8
                15 --- 12((12)) & 20((20))
            end
            classDef hidden display:none
        

        Cet arbre a bien pour hauteur $h = 4$. En comptant ses nœuds on obtient une taille de 8. On retrouve ce résultat avec la formule établie pour $t_{\text{min}}$ :

        $$\begin{align*} t_{\text{min}} &= 2^{h - 1} \\ &= 2^{4 - 1} \\ &= 2^3 \\ &= 8 \end{align*}$$

      • En conclusion, un ABR bien construit de hauteur $h = 4$ a une taille $t$ vérifiant :

        $$\begin{align*} 8 \leq t \leq 15 \end{align*}$$

      Cette plage de valeurs de taille correspond aux ABR obtenus en remplissant plus ou moins le niveau le plus profond (de 1 nœud à 8 nœuds dans l’exemple vu pour $h = 4$).

   2. Écrire la méthode bien_construit demandée.

      Réponse

      La question précédente permet d’identifier un ABR bien construit à l’aide de sa taille $t$ qui doit être comprise entre $t_{\text{min}}$ et $t_{\text{max}}$ c’est-à-dire vérifier l’encadrement suivant :

      $$\begin{align*} 2^{h-1} \leq t \leq 2^h - 1 \end{align*}$$

      On en déduit la méthode bien_construit de la classe Arbre.

      1 2 3 4

      def bien_construit(self): t = self.taille() h = self.hauteur() return 2**(h - 1) <= t and t <= 2**h - 1

2023, Sujet 21, Exercice 2. (Sujet et correction)

Correction commentée proposée en classe (à venir)

2023, Sujet 25, Exercice 2. (Sujet et correction)

Correction commentée proposée en classe (à venir)