Aller au contenu

Arbres binaires et arbres binaire de recherche

Arbre binaire : implémentation

Modélisation

On rappelle qu'un arbre binaire est constitué d'un ensemble (éventuellement vide) de nœuds. Si l'arbre binaire n'est pas vide, il possède un nœud particulier nommé la racine de l'arbre, munie la plupart du temps d'une étiquette. Les nœuds restants sont alors répartis entre le sous-arbre gauche et le sous-arbre droit.

Nous utiliserons dans ce TP deux classes pour implémenter les objets de type Arbre. La classe Noeud permet de représenter les nœuds de l'arbre. Il est à noter que l'étiquette sera toujours un entier dans ce TP, et que les attributs gauche et droit d'un nœud seront des objets de type ArbreBinaire dans cette partie.

1
2
3
4
5
class Noeud:
    def __init__(self, v, g, d):
        self.etiquette = v
        self.gauche = g
        self.droit = d

La seconde classe ArbreBinaire permet de représenter un arbre binaire. Un objet de type ArbreBinaire possède un unique attribut, racine, de type Nœud. On prendra pour convention que lorsque l'attribut racine vaut la valeur spéciale None, cela correspond à l'arbre vide. On remarquera l'utilisation de l'argument optionnel n dans la définition de la fonction __init__. Ainsi, il est possible d'instancier une variable a de type ArbreBinaire de deux manières différentes :

  • a = ArbreBinaire() : a.racine vaut alors None
  • a = ArbreBinaire(n), avec n un objet de type Noeud. a.racine est alors n.
###
def testpy-undArbreBinaire():bksl-nl """ Tests pour la méthode interface """bksl-nl print("Tests de ArbreBinaire.interface passés avec succès.")bksl-nl return Truebksl-nlbksl-nl# from tp import ArbreBinairebksl-nl# testpy-undArbreBinaire()bksl-nlbksl-nldef testpy-undArbreBinaire():bksl-nl """ Tests pour la méthode ajouterpy-unddepuispy-undtableau """bksl-nl print("Tests de ArbreBinaire.ajouterpy-unddepuispy-undtableau passés avec succès.")bksl-nl return Truebksl-nlbksl-nl# from tp import ArbreBinairebksl-nl# testpy-undArbreBinaire()bksl-nlbksl-nldef testpy-undArbreBinaire():bksl-nl """ Tests pour la méthode taille """bksl-nl print("Tests de ArbreBinaire.taille passés avec succès.")bksl-nl return Truebksl-nlbksl-nl# from tp import ArbreBinairebksl-nl# testpy-undArbreBinaire()bksl-nlbksl-nldef testpy-undArbreBinaire():bksl-nl """ Tests pour la méthode appartient """bksl-nl print("Tests de ArbreBinaire.appartient passés avec succès.")bksl-nl return Truebksl-nlbksl-nl# from tp import ArbreBinairebksl-nl# testpy-undArbreBinaire()bksl-nlbksl-nldef testpy-undArbreBinaire():bksl-nl """ Tests pour la méthode inserer """bksl-nl print("Tests de ArbreBinaire.inserer passés avec succès.")bksl-nl return Truebksl-nlbksl-nl# from tp import ArbreBinairebksl-nl# testpy-undArbreBinaire()bksl-nlbksl-nl 5/5

class Noeud:bksl-nl def py-undpy-undinitpy-undpy-und(self, v, g, d):bksl-nl self.etiquette = vbksl-nl self.gauche = gbksl-nl self.droit = dbksl-nlbksl-nlclass ArbreBinaire:bksl-nl """Représente un arbre binaire"""bksl-nl def py-undpy-undinitpy-undpy-und(self, n = None):bksl-nl """ArbreBinaire, Noeud -> NoneType"""bksl-nl self.racine = nbksl-nlbksl-nl def estpy-undvide(self):bksl-nl """ ArbreBinaire -> bool """bksl-nl return ...bksl-nl bksl-nl def etiquette(self):bksl-nl """ ArbreBinaire -> int """bksl-nl return ...bksl-nl bksl-nl def gauche(self):bksl-nl """ ArbreBinaire -> ArbreBinaire """bksl-nl return ...bksl-nl bksl-nl def droit(self):bksl-nl """ ArbreBinaire -> ArbreBinaire """bksl-nl return ...bksl-nl bksl-nl def estpy-undfeuille(self):bksl-nl """ ArbreBinaire -> bool """bksl-nl return ...bksl-nl bksl-nl def py-undpy-undstrpy-undpy-und(self):bksl-nl """ ArbreBinaire -> str """bksl-nl passbksl-nl bksl-nl def ajouterpy-unddepuispy-undtableau(self, tab):bksl-nl """ ArbreBinaire, [int] -> Nonetypebksl-nl Ajoute à l'arbre binaire self (supposé initiallement vide) les éléments de tab (correspondant à un parcours en largeur de l'arbre) """bksl-nl passbksl-nl bksl-nl def taille(self):bksl-nl """ ArbreBinaire -> intbksl-nl Renvoie le nombre de nœuds dont est composé self """bksl-nl passbksl-nl bksl-nl def appartient(self, e):bksl-nl """ ArbreBinaire, int -> boolbksl-nl Détermine si l'entier e est une étiquette de l'arbre self """bksl-nl passbksl-nl bksl-nl def inserer(self, e):bksl-nl """ ArbreBinaire, intbksl-nl Insère l'entier e dans l'arbre binaire self """bksl-nl passbksl-nlbksl-nl

On donne ci-dessous des exemples d'utilisation des classes Noeud et ArbreBinaire.

1
2
3
4
5
6
7
8
a_vide = ArbreBinaire()    
feuille1 = ArbreBinaire(Noeud(1,
                              ArbreBinaire(),
                              ArbreBinaire()))
feuille2 = ArbreBinaire(Noeud(2,
                              ArbreBinaire(),
                              ArbreBinaire()))
a0 = ArbreBinaire(Noeud(3, feuille1, feuille2))

Avec le code donné dans le sujet, il est à noter que :

  • ArbreBinaire() renvoie un objet de type ArbreBinaire dont l'attribut racine vaut None : il s'agit d'un arbre binaire vide.
  • La variable feuille1 est un objet de type ArbreBinaire. Sa racine est un objet de type Noeud, dont les attributs gauche et droit sont des objets de type ArbreBinaire.

  • Enfin, la variable a0 correspond à l'arbre binaire ci-dessous :

    img

Méthodes de l'interface

Compléter le code python des fonctions de l'interface du type ArbreBinaire, telles que décrites dans le cours.

Remarque. Si \(\mathcal{A}\) est un arbre binaire de racine r, et s1 (resp. s2) la chaîne de caractère représentant le sous-arbre gauche (resp. droit) de \(\mathcal{A}\), alors on représentera \(\mathcal{A}\) à l'aide de la chaîne de caractères :

({s1}) {r.etiquette} ({s2})

L'arbre vide sera représenté par la chaîne de caractère vide.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def est_vide(self):
    """ ArbreBinaire -> bool """
    return ...

def etiquette(self):
    """ ArbreBinaire -> int """
    return ...

def gauche(self):
    """ ArbreBinaire -> ArbreBinaire """
    return ...

def droit(self):
    """ ArbreBinaire -> ArbreBinaire """
    return ...

def est_feuille(self):
    """ ArbreBinaire -> bool """
    return ...

def __str__(self):
    """ ArbreBinaire -> str """
    pass

Méthode ajouter_depuis_tableau

On souhaite dans cette question écrire une méthode efficace pour créer un arbre binaire dont on fournit la liste la liste des étiquettes. tab est un tableau dont les éléments sont des entiers ou bien la valeur spéciale None, tel qu'obtenu avec un parcours en largeur de l'arbre binaire souhaité.

À l'aide du tableau tab, l'algorithme (similaire à celui d'un parcours en largeur) pour reconstruire l'arbre binaire self correspondant est le suivant :

  • l'arbre binaire initialement présent dans la file est self.
  • tant que tab n'est pas vide :
    • soit a le premier arbre de la file ;
    • soit elem le premier élément du tableau tab.
      • Si celui-ci n'est pas None : on affecte à la racine de a un Noeud d'étiquette elem et dont les deux enfants sont des arbres binaires vides.
      • Sinon on ne fait rien.
    • elem a été ajouté à l'arbre binaire en construction. On supprime donc elem de tab.
    • on ajoute les enfants gauche et droit de l'arbre a à la file dans le cas où a n'est pas l'arbre vide.
1
2
3
4
def ajouter_depuis_tableau(self, tab):
    """ ArbreBinaire, [int] -> Nonetype
    Ajoute à l'arbre binaire self (supposé initiallement vide) les éléments de tab (correspondant à un parcours en largeur de l'arbre) """
    pass

Méthode taille

Écrire une méthode taille de la classe ArbreBinaire qui renvoie le nombre de nœuds dont est constitué l'objet self.

1
2
3
4
def taille(self):
    """ ArbreBinaire -> int
    Renvoie le nombre de nœuds dont est composé self """
    pass

Méthode appartient

Écrire une méthode appartient de la classe ArbreBinaire qui détermine si l'élément e est une étiquette d'un des nœuds de self. 

1
2
3
4
def appartient(self, e):
    """ ArbreBinaire, int -> bool
    Détermine si l'entier e est une étiquette de l'arbre self """
    pass

Méthode inserer

Écrire une méthode inserer qui insère l'élément e dans l'arbre self de la manière suivante :

  • si self est vide, alors on affecte à son attribut racine un nœud d'étiquette e ;
  • sinon, on insère récursivement e dans le sous-arbre gauche ou droit de self qui possède le moins d'éléments (on pourra utiliser la méthode taille).
1
2
3
4
def inserer(self, e):
    """ ArbreBinaire, int
    Insère l'entier e dans l'arbre binaire self """
    pass

Arbre binaire de recherche

Définition

On appelle arbre binaire de recherche (ABR) un arbre binaire étiqueté qui vérifie les propriétés suivantes :

  • toutes les étiquettes de l'arbre appartiennent au même ensemble, et peuvent être comparées entres elles ;
  • le sous-arbre gauche est un arbre binaire de recherche dont toutes les étiquettes sont inférieures ou égales à l'étiquette de la racine ;
  • le sous-arbre droit est un arbre binaire de recherche dont toutes les étiquettes sont supérieures ou égales à l'étiquette de la racine.

  1. Parmi les arbres suivants, lesquels sont des arbres binaires de recherche ?

    img

  2. Citer les arbres binaires de recherche parmi les arbres \(\mathcal{A}_1\), \(\ldots\), \(\mathcal{A}_6\).

Implémentation

Un ABR est un arbre, dont les nœuds sont répartis de manière particulière. Ainsi, toutes les propriétés, toutes les méthodes s'appliquant aux arbres binaires s'appliquent également aux ABR. Attention cependant, la réciproque est fausse ! Si tout ABR est un arbre binaire, tout arbre binaire n'est pas un ABR.

Nous verrons que la structure d'ABR permet notamment d'optimiser certaines opérations, notamment la méthode appartient. On souhaite écrire une classe ABR afin de manipuler les arbres binaires de recherche. On pourrait copier/coller la classe ArbreBinaire, mais on aurait alors dupliqué notre code (c'est toujours une mauvaise idée). On utilise plutôt le concept d'héritage.

###
def testpy-undABR():bksl-nl """ Tests pour la méthode inserer """bksl-nl print("Tests de ABR.inserer passés avec succès.")bksl-nl return Truebksl-nlbksl-nl# from tp import ABRbksl-nl# testpy-undABR()bksl-nlbksl-nldef testpy-undABR():bksl-nl """ Tests pour la méthode appartient """bksl-nl print("Tests de ABR.appartient passés avec succès.")bksl-nl return Truebksl-nlbksl-nl# from tp import ABRbksl-nl# testpy-undABR()bksl-nlbksl-nldef testpy-undABR():bksl-nl """ Tests pour la méthode minimum """bksl-nl print("Tests de ABR.minimum passés avec succès.")bksl-nl return Truebksl-nlbksl-nl# from tp import ABRbksl-nl# testpy-undABR()bksl-nlbksl-nl 5/5

class ABR(ArbreBinaire):bksl-nl """ Représentation d'ABR (Arbre Binaire de Recherche) """bksl-nlbksl-nl def inserer(self, e):bksl-nl """ ABR, int -> NoneTypebksl-nl Insère l'élément e dans l'ABR self """bksl-nl passbksl-nl bksl-nl def appartient(self, e):bksl-nl """ ABR, int -> Nonetypebksl-nl Détermine si l'élément e est une des étiquettes de l'ABR self """bksl-nl passbksl-nl bksl-nl def minimum(self):bksl-nl """ ABR -> intbksl-nl Renvoie la plus petite étiquette de self """bksl-nl passbksl-nlbksl-nl

On dit avec cette syntaxe que la classe ABR hérite de la classe ArbreBinaire : les objets de type ABR possèdent toutes les méthodes des objets de type ArbreBinaire (en particulier la méthode __init__ : leurs attributs sont donc égalements les mêmes).

Exemple

On donne ci-dessous un exemple d'utilisation de la classe ABR.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
abr_vide = ABR()    
feuille1 = ABR(Noeud(1,
                     ABR(),
                     ABR()))
feuille2 = ABR(Noeud(3,
                     ABR(),
                     ABR()))
a11 = ABR(Noeud(2, feuille1, feuille2))

print(a11)
print(a11.taille())
print(a11.appartient(4))

(() 1 ()) 2 (() 3 ())
3
False

Méthode inserer

Écrire la méthode inserer de la classe ABR qui insère l'élément e au bon endroit dans l'ABR self : en particulier, self sera toujours un ABR à l'issue de l'exécution de la méthode inserer.

1
2
3
4
def inserer(self, e):
    """ ABR, int -> NoneType
    Insère l'élément e dans l'ABR self """
    pass

Méthode appartient

Écrire une méthode appartient de la classe ABR qui détermine si l'élément e est une étiquettes d'un des nœuds de self. On fera attention à ne réaliser au plus qu'un seul appel récursif.

1
2
3
4
def appartient(self, e):
    """ ABR, int -> Nonetype
    Détermine si l'élément e est une des étiquettes de l'ABR self """
    pass

Méthode minimum

Écrire une méthode minimum de la classe ABR qui renvoie la plus petite étiquette présent dans self. On fera attention à ne réaliser au plus qu'un seul appel récursif.

1
2
3
4
def minimum(self):
    """ ABR -> int
    Renvoie la plus petite étiquette de self """
    pass

À propos de l'héritage

  1. Commenter l'affichage suivant :

    1
2
3
4
    print(a11.taille)
print(a11.ajouter_depuis_tableau)
print(a11.appartient)
print(a11.minimum)

    <bound method ArbreBinaire.taille of <__main__.ABR object at 0x7fa7139f9270>>
<bound method ArbreBinaire.ajouter_depuis_tableau of <__main__.ABR object at 0x7fa7139f9270>>
<bound method ABR.appartient of <__main__.ABR object at 0x7fa7139f9270>>
<bound method ABR.minimum of <__main__.ABR object at 0x7fa7139f9270>>

  2. Commenter l'affichage :

    1
2
3
4
5
    a12 = ABR()
a12.ajouter_depuis_tableau([2, 1, 3])       
print(a12)
a12.inserer(5)
print(a12)

    (() 1 ()) 2 (() 3 ())
(() 1 ()) 2 ((() 5 ()) 3 ())

  3. Proposer une méthode ajouter_depuis_tableau de la classe ABR qui étant donné un ABR self supposé vide le rempli avec les éléments de tab. À l'issue de l'exécution de cette méthode, self est toujours un ABR.

Documents