====== Exercice : Arbre binaire de recherche ======

<WRAP box>Il s'agit de l'exercice 3 de ce {{ .:spe-numerique-informatique-2021-metro-cand-libre-2-sujet-officiel.pdf |sujet}}</WRAP>

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

<WRAP tip>
On rappelle qu'un arbre binaire est composé de nœuds, chacun des nœuds possédant éventuellement un sous-arbre gauche et éventuellement un sous-arbre droit. Un nœud sans sous-arbre est appelé feuille. 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. Ainsi la hauteur d’un arbre réduit à un nœud, c’est-à-dire la racine, est 1.

Dans un arbre binaire de recherche, 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 de cet arbre sont toutes distinctes.

Un arbre binaire de recherche est dit « bien construit » s’il n'existe pas d'arbre de hauteur
inférieure qui pourrait contenir tous ses nœuds.
</WRAP>

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

{{ .:arbre_binaire_recherche.png?direct&600 |}}

=== Question 1 ===

  - Quelle est la taille de l'arbre ci-dessus ?
  - Quelle est sa hauteur ?

=== Question 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.

=== Question 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é.

<code python>
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)
</code>

Donner la représentation de l’arbre codé par les instructions ci-dessous.

<code python>
a = Arbre(10)
a.insere(20)
a.insere(15)
a.insere(12)
a.insere(8)
a.insere(4)
a.insere(5)
</code>

=== Question 4 ===

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

<wrap tip>N'hésitez pas à améliorer cette fonction : cet enchaînement de tests n'est pas terrible :-|</wrap>

<code python>
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
</code>

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

=== Question 5 ===

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

=== Question 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$.

  - Quelle est la taille minimale, notée $t_{min}$, d'un arbre binaire de recherche « bien construit » de hauteur $h$ ?
  - Écrire la méthode ''bien_construit'' demandée.