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.

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

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 :

Méthodes de l'interface de base¶

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.

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 (qui indique la présence d'un arbre vide), 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 la file des éléments a parcourir n'est pas vide :
- on défile le premier élément a de la file ;
- on défile le premier élément e de 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.
- on ajoute les enfants gauche et droit de l'arbre a à la file lorsque cela est possible.

def ajouter_depuis_tableau(self, tab):
    """ ArbreBinaire, [int] -> None
    Ajoute à l'arbre binaire self (supposé initiallement vide) les éléments de tab (correspondant à un parcours en largeur) """
    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.

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.

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

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.

Parmi les arbres suivants, lesquels sont des arbres binaires de recherche ?
Citer les arbres binaires de recherche parmi les arbres \(\mathcal{A}_1\), \(\ldots\), \(\mathcal{A}_6\).
Pour chacun des arbres binaires de recherche parmi les arbres \(\mathcal{A}_1\), \ldots, \(\mathcal{A}_{11}\), donner l'ordre des étiquettes lorsque celui-ci est parcouru en profondeur d'abord, de manière infixe.

Que constate-t-on ?
Dessiner un ABR de hauteur 2 et un ABR de hauteur 4 contenant tous les deux les valeurs 3, 6, 149, 7, 80, 4.

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, par exemple la méthode appartient, ou la méthode inserer. On souhaite écrire une classe ABR afin de manipuler les arbres binaires de recherche.

###

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

Exemple¶

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

abr_vide = ABR()    
abr_feuille1 = ABR(Noeud(1, ABR(), ABR()))
abr_feuille2 = ABR(Noeud(3, ABR(), ABR()))
a11 = ABR(Noeud(2, abr_feuille1, abr_feuille2))
print(a11)

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

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. On effectuera au plus un appel récursif. Pour cela, dans le cas général, on distinguera deux cas :

soit l'élement e est inférieur ou égal à l'étiquette de la racine ;
soit l'élément e est strictement supérieur à l'étiquette de la racine.

def inserer(self, e):
    """ ABR, int -> None
    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. On pourra pour cela s'inspirer de l'algorithme de la méthode inserer et distinguer plusieurs cas en comparant e à l'étiquette de la racine.

def appartient(self, e):
    """ ABR, int -> None
    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ésente dans self. On fera attention à ne réaliser au plus qu'un seul appel récursif.

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

Application : tri d'un tableau¶

Les arbres binaires de recherche sont très efficace lorsqu'il s'agit de comparer des éléments entre eux. Une des applications principale des arbres binaires de recherche est le tri de tableaux.

D'un tableau à l'ABR¶

Écrire une fonction tableau_vers_abr qui étant donné un tableau t renvoie un arbre binaire de recherche dont les étiquettes sont les valeurs présentes dans le tableau.

###

De l'ABR au tableau trié¶

Écrire une fonction stocke qui étant donné un arbre binaire de recherche A et une liste l ajoute à l les éléments de A lorsque celui-ci est parcouru de manière infixe.

###

Tri d'un tableau à l'aide d'un ABR¶

Écrire une fonction trie qui prend en argument un tableau d'entiers tab et qui renvoie le tableau trié. Vous utiliserez pour cela un parcours infixe d'un arbre binaire de recherche.

###

Arbres binaires et arbres binaire de recherche

Arbre binaire : implémentation¶

Modélisation¶

Méthodes de l'interface de base¶

Méthode ajouter_depuis_tableau¶

Méthode taille¶

Méthode appartient¶

Méthode inserer¶

Arbre binaire de recherche¶

Définition¶

Implémentation¶

Exemple¶

Méthode inserer¶

Méthode appartient¶

Méthode minimum¶

Application : tri d'un tableau¶

D'un tableau à l'ABR¶

De l'ABR au tableau trié¶

Tri d'un tableau à l'aide d'un ABR¶

Méthode `ajouter_depuis_tableau`¶

Méthode `taille`¶

Méthode `appartient`¶

Méthode `inserer`¶

Méthode `inserer`¶

Méthode `appartient`¶

Méthode `minimum`¶