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

On considère l’arbre binaire de recherche ci-dessous.

1. Concernant l'arbre ci-dessus,
   1. Quelle est sa taille ?
   2. Quelle est sa hauteur ?
2. Cet arbre binaire de recherche n'est pas « bien construit ». Proposer un arbre binaire de recherche contenant les mêmes clés et dont la hauteur est plus petite que celle de l’arbre initial.
3. Les classes Noeud et Arbre ci-dessous permettent de mettre en œuvre en Python la structure d'arbre binaire de recherche. La méthode insere permet d’insérer récursivement une nouvelle clé.

   class Noeud:
       def __init__(self, cle):
           self.cle = cle
           self.gauche = None
           self.droit = 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.droit == None :
                   self.droit = Noeud(cle)
               else :
                   self.droit.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 codé par les instructions ci-dessous.

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

4. Pour calculer la hauteur d'un arbre non vide, on a écrit la méthode ci-dessous dans la classe Noeud.
   N'hésitez pas à améliorer cette fonction : cet enchaînement de tests n'est pas terrible

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

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

5. Écrire les méthodes taille des classes Noeud et Arbre permettant de calculer la taille d’un arbre.
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 arbre binaire de recherche de hauteur $h$ est $2^h-1$.
   1. Quelle est la taille minimale, notée $t_{min}$, d'un arbre binaire de recherche « bien construit » de hauteur $ℎ$ ?
   2. Écrire la méthode bien_construit demandée.