Exercice : Arbre binaire de recherche

Il s'agit de l'exercice 3 de ce sujet

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

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

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

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)

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

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.