Aller au contenu

21-NSIJ2ME2 Exercice 3⚓︎

Thème : les arbres binaires de recherche et la POO.

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\).

Remarque

Ce rappel du vocabulaire est-il nécessaire ? Préciser pour la suite la définition de hauteur retenue oui mais le reste est censé être connu. De plus le texte de ce rappel est un peu maladroit, oubliant de préciser ce qu'est une racine, mais y faisant référence par deux fois.

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.

L'ABR du sujet

abr

Question 1a

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

Réponse

La taille de l'arbre est \(7\).

Question 1b

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

Réponse

Compte tenu de la définition retenue la hauteur de cet arbre est \(4\) (par exemple en suivant la branche \(12\), \(10\), \(5\) et \(8\)).

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.

Réponse

ABR équilibré

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

Implémentation d'un ABR avec 2 classes

Cette implémentation n'est pas satisfaisante : tout se passe au niveau d'un nœud qui peut être inexistant (None), compliquant les choses.

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)
Question 3

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)
Réponse

arbre de la Q3

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

Remarque

Cette implémentation de la hauteur n'est pas raisonnable.

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

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

Réponse
class Arbre:
    ...
    def hauteur(self):
        return self.racine.hauteur()
Une implémentation simple

Voilà ce que pourrait être une implémentation d'ABR et la méthode hauteur :

class ABR:

    def __init__(self, v=None):
        self.valeur = v
        if v is not None:
            self.gauche = ABR()
            self.droit = ABR()

    def est_vide(self):
        return self.valeur is None

    def insere(self, v):
        if self.est_vide():
            self.valeur = v
            self.gauche = ABR()
            self.droit = ABR()
        elif v < self.valeur:
            self.gauche.insere(v)
        else:
            self.droit.insere(v)                    

    def hauteur(self):
        if self.est_vide():
            return 0
        else:
            return 1 + max(self.gauche.hauteur(), self.droit.hauteur())
Question 5

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

Réponse

Avec l'implémentation proposée par le sujet les deux méthodes taille sont :

class Noeud:
    ...
    def taille(self):
        if self.gauche == None and self.droit == None:
            return 1
        if self.gauche == None:
            return 1 + self.droit.taille()
        elif self.droit == None:
            return 1 + self.gauche.taille()
        else:
            return 1 + self.gauche.taille() + self.droit.taille()

class Arbre:
    ...
    def taille(self):
        return self.racine.taille()
Remarque

Avec notre implémentation la classe ABR peut disposer d'une méthode taille très simple :

class ABR:
    ...
    def taille(self):
        if self.est_vide():
            return 0
        else:
            return 1 + self.gauche.taille() + self.droit.taille()

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\)

Question 6a

Quelle la taille minimale, notée \(t_{min}\), d'un arbre binaire de recherche "bien construit" de hauteur \(h\) ?

Réponse

Soit \(A\) un ABR "bien construit" de hauteur \(h - 1\) de taille maximale. On sait que cet arbre possède \(2^{h-1} - 1\) nœuds.Si on ajoute un seul nœud alors cet arbre aura une hauteur de \(h\) et son nombre de nœuds vaudra : \(2^{h-1} - 1 + 1\). On en déduit donc que :

\[t_{min}(h) = 2^{h-1}\]
Question 6b

Écrire la méthode bien_construit demandée.

Réponse

On déduit des questions précédentes qu'un arbre bien construit à une taille comprise entre \(2^{h-1}\) et \(2^h - 1\) :

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