20 - Implémenter un AB

⏪

⏬

⏩

1 - objet

2 - Tuple

3 - dict+list

4 - Tableau

5 -

Nous allons voir différentes façons d'implémenter les Arbres, et voir ce qui change alors dans vos programmes Python.

Prérequis :

Données : Arbre et Arbre Binaire
Algo : Parcours d'Arbres
Algo : Algorithmes des Arbres Binaires

Evaluation ✎ :

Documents de cours : open document ou pdf

Résumé : Version HTML ou fond blanc ou ou PDF (couleur ou gris)

MODE COURS (cacher les questions)

1 - Avec un modèle objet

⇩ ⇧ ⤊

Beaucoup de blabla dans cette partie car on y présente des variantes de la classe AB utilisée lors de vos séances de TP.

La classe basique utilisée sur ce site

Nous avons pour le moment utilisé un modèle objet très simple basé sur une seule classe nommée AB.

1.0 Arbre binaire : modèle objet où AB NON VIDE et Noeud sont des alias

Voir

C'est le modèle utilisé sur la plupart des TP de ce site.

Remarques générales

Avec ce modèle, il n'y a pas de différence entre un Noeud et un Arbre Binaire NON VIDE : ce sont deux alias vers le même contenu mémoire.

La classe ne contient que trois attributs : valeur, gauche et droite.

IMPORTANT : le seul cas où on peut envoyer une valeur None est pour l'Arbre Binaire VIDE.

class AB:
    """Implémentation d'un Arbre Binaire sous forme objet simple"""
 
    def __init__(self, valeur, gauche, droite):
        self.v = valeur  # valeur attribuée à la racine
        self.g = gauche  # Référence du sous-arbre gauche ou None si on atteint un Arbre Binaire Vide
        self.d = droite  # Référence du sous-arbre droite ou None si on atteint un Arbre Binaire Vide

Implémentation

"""Module implémentant un Arbre Binaire (AB) avec un modèle objet
 
Coûts et prototypes des primitives disponibles :
 
[cst] nv_ABV() -> 'AB VIDE'
[cst] nv_AB(valeur:'Element', g:'AB', d:'AB') -> 'AB NON VIDE'
[cst] est_ABV(arbre:'AB') -> bool
[cst] racine(arbre:'AB NON VIDE') -> 'Noeud'
[cst] gauche(arbre:'AB NON VIDE') -> 'AB'
[cst] droite(arbre:'AB NON VIDE') -> 'AB'
 
[cst] contenu(noeud:'Noeud') -> 'Element'
"""
 
# Déclaration de la classe AB
 
class AB:
    """Implémentation d'un Arbre Binaire"""
 
    def __init__(self, valeur, gauche, droite):
     
        self.v = valeur
        self.g = gauche
        self.d = droite
     
    def relier_a_gauche(self:'AB NON VIDE', sous_arbre:'AB'):
        """Méthode qui définit sous_arbre comme le sous-arbre gauche de l'arbre actif"""
        self.g = sous_arbre
 
    def relier_a_droite(self:'AB NON VIDE', sous_arbre:'AB'):
        """Méthode qui définit sous_arbre comme le sous-arbre droite de l'arbre actif"""
        self.d = sous_arbre
 
    def definir_donnees_racine(self:'AB', element:'Element NON VIDE'):
        """Méthode qui place l'élément NON VIDE en tant que racine de l'arbre"""
        self.v = element
 
    def vider(self:'AB'):
        """Méthode qui transforme l'arbre en AB VIDE"""
        self.v = None
        self.g = None
        self.d = None
 
# Fonctions d'interface (accessibles de l'extérieur)
 
def contenu(noeud:'Noeud') -> 'Element':
    """Renvoie le contenu associé au noeud fourni"""
    return noeud.v
 
def nv_ABV() -> 'AB VIDE':
    """Renvoie un nouvel Arbre Binaire Vide"""
    return AB(None, None, None)
 
def nv_AB(valeur:'Element', g:'AB', d:'AB') -> 'AB NON VIDE':
    """Renvoie un nouvel Arbre Binaire dont la racine porte valeur et qui mène aux sous-arbres g et d"""
    return AB(valeur, g, d)
 
def est_ABV(arbre:'AB') -> bool:
    """Prédicat qui renvoie True si l'arbre est vide"""
    return arbre.v is None and arbre.g is None and arbre.d is None
 
def racine(arbre:'AB NON VIDE') -> 'Noeud':
    """Renvoie le noeud-racine de l'Arbre Binaire NON VIDE"""
    return arbre  # ici arbre et racine sont des alias
 
def gauche(arbre:'AB NON VIDE') -> 'AB':
    """Renvoie le sous-arbre gauche de l'Arbre Binaire NON VIDE"""
    return arbre.g
 
def droite(arbre:'AB NON VIDE') -> 'AB':
    """Renvoie le sous-arbre droite de l'Arbre Binaire NON VIDE"""
    return arbre.d
 
# Programme de test du module
 
if __name__ == "__main__":
 
    ad = nv_AB("D", nv_ABV(), nv_ABV())
    af = nv_AB("F", ad,  nv_ABV())
    ae = nv_AB("E",  nv_ABV(), af)
    ah = nv_AB("H", nv_ABV(), nv_ABV())
    ag = nv_AB("G", nv_ABV(), ah)
    ab = nv_AB("B", nv_ABV(), nv_ABV())
    ac = nv_AB("C", ag, ab)
    aa = nv_AB("A", ac, ae)
    print(contenu(racine(gauche(aa))))

Génération d'arbres et de noeuds

On donne à chaque fois
l'utilisation directe du modèle suivi de
l'utilisation des fonctions-primitives founies dans le module.

Un Arbre Binaire VIDE est créé avec
AB(None, None, None)
nv_ABV()

Un Arbre Binaire NON VIDE est créé avec
AB(valeur, arbre_gauche, arbre_droite)
nv_AB(valeur, arbre_gauche, arbre_droite)

Un Arbre Binaire NON VIDE avec un sous-arbre gauche vide est créé avec
AB(valeur, AB(None, None, None), arbre_droite)
nv_AB(valeur, nv_ABV(), arbre_droite)

Un Arbre Binaire NON VIDE avec un sous-arbre droite vide est créé avec
AB(valeur, arbre_gauche, AB(None, None, None))
nv_AB(valeur, arbre_droite, nv_ABV())

Une feuille est créée avec
AB(valeur, AB(None, None, None), AB(None, None, None))
nv_AB(valeur, nv_ABV(), nb_ABV())

Variante 1 : fournir des valeurs par défaut

01° Créer des arbres ou des feuilles nécessite à chaque fois d'indiquer les sous-arbres, même s'ils sont des arbres binaires vides.

On peut simplifier l'écriture en utilisant les valeurs par défaut : voir la ligne 4.

class AB:
    """Implémentation d'un Arbre Binaire sous forme objet simple"""
 
    def __init__(self, valeur=None, gauche=None, droite=None):
        self.v = valeur  # valeur attribuée à la racine
        self.g = gauche  # Référence du sous-arbre gauche ou None si on atteint un Arbre Binaire Vide
        self.d = droite  # Référence du sous-arbre droite ou None si on atteint un Arbre Binaire Vide

Questions

A quoi correspondent les valeurs None qu'on trouve sur la ligne 4 de cette variante de la classe AB ?
Comment peut-on utiliser le constructeur pour créer une Arbre VIDE de façon plus courte ?
Comment peut-on utiliser le constructeur pour créer une Feuille ?

Correction ?

...CORRECTION...

Ce sont des valeurs par défaut, utilisées uniquement si on réalise un appel sans envoyer des valeurs pour ces paramètres.
Arbre vide : AB() qui sera transformé en AB(None, None, None) pour compléter les valeurs manquantes.
Feuille : AB(valeur, AB(), AB()) qui sera transformé en AB(valeur, AB(None, None, None), AB(None, None, None)) pour compléter les valeurs manquantes.

Le bilan suivant est à lire en diagonale uniquement : il est là surtout pour vous permettre de reprendre le code si vous en avez besoin en projet.

1.1 Arbre binaire : modèle objet avec valeur par défaut

Voir

Remarques

Créer des arbres ou des feuilles nécessite à chaque fois d'indiquer les sous-arbres, même s'ils sont des arbres binaires vides.

On peut simplifier l'écriture en utilisant les valeurs par défaut : voir la ligne 4.

class AB:
    """Implémentation d'un Arbre Binaire sous forme objet simple"""
 
    def __init__(self, valeur=None, gauche=None, droite=None):
        self.v = valeur  # valeur attribuée à la racine
        self.g = gauche  # Référence du sous-arbre gauche ou None si on atteint un Arbre Binaire Vide
        self.d = droite  # Référence du sous-arbre droite ou None si on atteint un Arbre Binaire Vide

Cela veut dire qu'on peut se permettre de ne pas envoyer certaines valeurs. Dans ce cas, elles seront initialisées à None comme indiqué dans le code.

Génération d'arbres et de noeuds : plus facile

On donne à chaque fois
l'utilisation directe du modèle suivi de
l'utilisation des fonctions-primitives founies dans le module.

Un Arbre Binaire VIDE est créé avec
AB()
nv_ABV()

Un Arbre Binaire NON VIDE est créé avec
AB(valeur, arbre_gauche, arbre_droite)
nv_AB(valeur, arbre_gauche, arbre_droite)

Un Arbre Binaire NON VIDE avec un sous-arbre gauche vide est créé avec
AB(valeur, AB(), arbre_droite)
nv_AB(valeur, nv_ABV(), arbre_droite)

Un Arbre Binaire NON VIDE avec un sous-arbre droite vide est créé avec
AB(valeur, arbre_gauche, AB())
nv_AB(valeur, arbre_droite, nv_ABV())

Une feuille est créée avec
AB(valeur, AB(), AB())
nv_AB(valeur, nv_ABV(), nb_ABV())

Implémentation

"""Module implémentant un Arbre Binaire (AB) avec un modèle objet
 
Coûts et prototypes des primitives disponibles :
 
[cst] nv_ABV() -> 'AB VIDE'
[cst] nv_AB(valeur:'Element', g:'AB', d:'AB') -> 'AB NON VIDE'
[cst] est_ABV(arbre:'AB') -> bool
[cst] racine(arbre:'AB NON VIDE') -> 'Noeud'
[cst] gauche(arbre:'AB NON VIDE') -> 'AB'
[cst] droite(arbre:'AB NON VIDE') -> 'AB'
 
[cst] contenu(noeud:'Noeud') -> 'Element'
"""
 
# Déclaration de la classe AB
 
class AB:
    """Implémentation d'un Arbre Binaire"""
 
    def __init__(self, valeur=None, gauche=None, droite=None):
     
        self.v = valeur
        self.g = gauche
        self.d = droite
     
    # Le reste est inchangé 

Variante 2 : uniquement les Noeuds

Dans certains sujets, on ne définit qu'une classe Noeud. On ne peut donc pas gérer directement l'arbre binaire vide puisqu'il ne possède pas de noeud par définition...

1.2 Arbre binaire NON VIDE : Noeud avec un modèle objet

Voir

Remarques

Un Arbre binaire possède une valeur de racine et possède toujours deux sous-arbres binaires (qui peuvent être un objet arbre VIDE AB(), pas None directement).

Un Noeud d'arbre binaire possède une valeur et possède au maximum deux enfants : ils sont donc des Noeuds ou rien. Cette fois, on pourra utiliser None pour indiquer l'absence de noeud enfant.

class Noeud:
    """Implémentation d'unNoeud sous forme objet simple"""
 
    def __init__(self, valeur=None, enfant_gauche=None, enfant_droite=None):
        self.v = valeur  # valeur attribuée à la racine
        self.g = enfant_gauche  # Référence du noeud à gauche, ou None
        self.d = enfant_droite  # Référence du noeud à droite, ou None

Génération de noeuds

Un Arbre Binaire VIDE : impossible avec la classe Noeud, à moins de considérer qu'un triplet d'attributs Noeud(None, None, None) encode l'arbre vide. Mais c'est "bizarre" de créer un Noeud pour un arbre vide, qui par définition ne contient pas de Noeud justement.

La plupart du temps, avec cette implémentation, on prend None comme valeur d'encodage de l'arbre binaire VIDE. Simple sur les arbres qui n'évoluent pas mais choix embêtant si on doit insérer/supprimer régulièrement.

Un Noeud est créé avec
Noeud(valeur, noeud_gauche, noeud_droite)

Un Noeud avec uniquement un enfant droite:
Noeud(valeur, None, noeud_droite)

Un Noeud avec uniquement un enfant gauche :
Noeud(valeur, enfant_gauche, None) si valeurs par défaut

Une feuille est créée avec
Noeud(valeur, None, None)

Variante 3 : une classe AB et une classe Noeud

On peut revenir à quelque chose de proche du type abstrait en distinguant dans le code les arbres et les noeuds.

1.3 Arbre binaire et Noeud avec un modèle objet

Voir

Remarques générales

Cette fois l'arbre NON VIDE n'est pas un alias de son Noeud-Racine mais une référence vers son Noeud racine.

L'arbre binaire VIDE et NON VIDE sont définis comme des instances de la classe AB.

Un noeud est une instance de la classe Noeud.

Implémentation

class Noeud:
    """Implémentation d'un Noeud sous forme objet simple"""
 
    def __init__(self, valeur=None, enfant_gauche=None, enfant_droite=None):
        self.v = valeur  # valeur attribuée à la racine
        self.g = enfant_gauche  # Référence du noeud à gauche, ou None
        self.d = enfant_droite  # Référence du noeud à droite, ou None
 
class AB:
    """Implémentation d'un AB VIDE ou NON VIDE sous forme objet"""
 
    def __init(self, racine=None):
        self.r = racine  # une instance de Noeud si NON VIDE ou None si VIDE
 
if __name__ == "__main__":
    arb_vide = AB()  # Ici on envoie None par défaut
    c = Noeud("C")        # c est une feuille ne contenant que "C"
    b = Noeud("B")        # b est une feuille ne contenant que "B"
    a = Noeud("A", b, c)  # a est un Noeud contenant "A" et menant à b et c
    arb_a = AB(a)         # arb_a est un Arbre Binaire de racine a

Mini variante : triplet (g, r, d) plutôt que (r, g, d)

On note parfois le triplet en plaçant la valeur de la racine au milieu.

02° Une expression arithmétique ne comportant que les quatre opérations +, -, *, ÷ peut être représentée sous forme d’arbre binaire. Les nœuds internes sont des opérateurs et les feuilles sont des nombres.

Dans un tel arbre, la disposition des nœuds joue le rôle des parenthèses.

En parcourant en profondeur infixe l’arbre binaire ci-dessus, on retrouve l’expression notée habituellement :

(3 * (8 + 7)) - (2 + 1)

La classe Expr permet d’implémenter une structure d’arbre binaire pour représenter de telles expressions.

Compléter la méthode récursive infixe qui renvoie une chaîne de caractères contenant des parenthèses représentant l’expression arithmétique sur laquelle on l’applique.

class Expr:
    """Classe implémentant un arbre d'expression."""
 
    def __init__(self, g:'None|Expr', v:'int|str', d:'None|Expr'):
        """un objet Expr possède 3 attributs """
 
        self.gauche = g  # la sous-expression gauche
        self.valeur = v  # valeur de l'étiquette, opérande ou nombre
        self.droite = d  # la sous-expression droite
 
 
    def est_une_feuille(self) -> bool:
        """renvoie True SSI le noeud est une feuille"""
 
        return self.gauche is None and self.droite is None
 
 
    def infixe(self) -> str:
        """renvoie la représentation infixe de l'expression"""
 
        s = ... 
        if self.gauche is not None:
            s = '(' + s + ... .infixe() 
        s = s + ... 
        if ... is not None: 
            s = s + ... + ... 
        return s

Exemples d'utilisation (attention, dans les vrais sujets Type 2 les types ne sont presque jamais indiqués dans la documentation mais sont retrouvables via les exemples et/ou le code.)


>>> a = Expr(Expr(None, 1, None), '+', Expr(None, 2, None))
>>> a.infixe()
'(1+2)'
 
>>> b = Expr(Expr(Expr(None, 1, None), '+', Expr(None, 2, None)), '*', Expr(Expr(None, 3, None), '+', Expr(None, 4, None)))
>>> b.infixe()
'((1+2)*(3+4))'
 
>>> e = Expr(Expr(Expr(None, 3, None), '*', Expr(Expr(None, 8, None), '+', Expr(None, 7, None))), '-', Expr(Expr(None, 2, None), '+', Expr(None, 1, None)))
>>> e.infixe()
'((3*(8+7))-(2+1))

Correction ?

...CORRECTION...

REMARQUE : puisque la méthode travaille sur un objet self, c'est que c'est un Noeud, cela ne peut pas être un cas vide.

REMARQUE 2 : le sujet suppose des opérateurs binaires : si il y a un enfant gauche, il y a visiblement toujours un enfant droite.

class Expr:
    """Classe implémentant un arbre d'expression."""
 
    def __init__(self, g:'None|Expr', v:'int|str', d:'None|Expr'):
        """un objet Expr possède 3 attributs """
 
        self.gauche = g  # la sous-expression gauche
        self.valeur = v  # valeur de l'étiquette, opérande ou nombre
        self.droite = d  # la sous-expression droite
 
 
    def est_une_feuille(self) -> bool:
        """renvoie True SSI le noeud est une feuille"""
 
        return self.gauche is None and self.droite is None
 
 
    def infixe(self) -> str:
        """renvoie la représentation infixe de l'expression"""
 
        s = "" 
        if self.gauche is not None:
            s = '(' + s + self.gauche.infixe() 
        s = s + str(self.valeur)
        if self.droite is not None: 
            s = s + self.droite.infixe() + ")" 
        return s

03° Un arbre binaire est soit vide, représenté en Python par la valeur None, soit un nœud, contenant une étiquette et deux sous-arbres gauche et droit et représenté par une instance de la classe Noeud donnée ci-dessous.

class Noeud:
    """Implémentation d'un Noeud sous forme objet simple"""
 
    def __init__(self, valeur, enfant_gauche, enfant_droite):
        self.v = valeur  # valeur attribuée à la racine
        self.g = enfant_gauche  # Référence du noeud à gauche, ou None
        self.d = enfant_droite  # Référence du noeud à droite, ou None

L’arbre NON VIDE ci-dessous sera donc implémenté de la manière suivante, en considérant qu'il n'est qu'un alias vers son noeud-racine :


>>> a = Noeud(1, Noeud(4, None, None), Noeud(0, None, Noeud(7, None, None)))

Convention : on considère que la hauteur d’un arbre vide est -1 et la taille d’un arbre vide est 0.

Écrire une fonction récursive taille() prenant en paramètre un arbre a et qui renvoie la taille de l’arbre que cette instance implémente.

Écrire une fonction récursive hauteur() prenant en paramètre un arbre a et qui renvoie la hauteur de l’arbre que cette instance implémente.

Correction ?

...CORRECTION...

class Noeud:
    """Implémentation d'un Noeud sous forme objet simple"""
 
    def __init__(self, valeur, enfant_gauche, enfant_droite):
        self.v = valeur  # valeur attribuée à la racine
        self.g = enfant_gauche  # Référence du noeud à gauche, ou None
        self.d = enfant_droite  # Référence du noeud à droite, ou None
 
 
def taille(a:'Noeud|None') -> int:
    """Renvoie la taille de l'arbre NON VIDE dont la racine est a ou d'un arbre VIDE"""
 
    if a is None:  # si l'arbre est VIDE, presque équivalent de a == None
        return 0
    else:
        return 1 + taille(a.g) + taille(a.d)
 
def hauteur(a:'Noeud|None') -> int:
    """Renvoie la hauteur de l'arbre NON VIDE dont la racine est a ou d'un arbre VIDE"""
 
    if a is None:  # si l'arbre est VIDE, presque équivalent de a == None
        return -1
    else:
        return 1 + max(hauteur(a.g), hauteur(a.d))
 
 
 
if __name__ == "__main__":
    a = Noeud(1, Noeud(4, None, None), Noeud(0, None, Noeud(7, None, None)))
 
    n = taille(a)
    assert n == 4
    assert taille(None) == 0
    print('Tests taille : ok')
 
    h = hauteur(a)    
    assert h == 2
    assert hauteur(None) == -1
    print('Tests hauteur : ok')

04° Un arbre binaire est soit vide, représenté en Python par la valeur None, soit un nœud, contenant une étiquette et deux sous-arbres gauche et droite et représenté par une instance de la classe Noeud donnée ci-dessous.

class Noeud:
    """Classe représentant un noeud d'un arbre binaire"""
    def __init__(self, etiquette, gauche, droit):
        """Crée un noeud de valeur etiquette avec 
        gauche et droit comme fils."""
        self.etiquette = etiquette
        self.gauche = gauche
        self.droit = droit
 
 
def parcours(arbre, liste):
    """parcours récursivement l'arbre en ajoutant les étiquettes
    de ses noeuds à la liste passée en argument en ordre infixe."""
    if arbre != None:
        parcours(arbre.gauche, liste)
        liste.append(arbre.etiquette)
        parcours(arbre.droit, liste)
     
 
 
def insere(arbre, cle):
    """insere la cle dans l'arbre binaire de recherche représenté par arbre.
    Renvoie l'arbre modifié."""
 
    if arbre == None:
        return Noeud(cle, None, None) # creation d'une feuille
    else:
        if ...:
            arbre.gauche = insere(arbre.gauche, cle)
        else:
            arbre.droit = ...
        return arbre

La fonction récursive parcours() renvoie la liste des étiquettes des nœuds de l’arbre implémenté par l’instance arbre dans l’ordre du parcours en profondeur infixe à partir d’une liste vide passée en argument.

Compléter le code de la fonction insere() qui prend en argument un arbre binaire de recherche arbre représenté ainsi et une étiquette cle (non présente dans l’arbre, pas de doublon) et qui :

renvoie une nouvelle feuille d’étiquette cle s’il est vide ;
renvoie l’arbre après l’avoir modifié en insérant cle sinon ;
garantit que l’arbre ainsi complété soit encore un arbre binaire de recherche.

Tester ensuite ce code en utilisant la fonction parcours() et en insérant successivement des nœuds d’étiquette 1, 4, 6 et 8 dans l’arbre binaire de recherche représenté ci- dessous :

Correction ?

...CORRECTION...

class Noeud:
    """Classe représentant un noeud d'un arbre binaire"""
    def __init__(self, etiquette, gauche, droit):
        """Crée un noeud de valeur etiquette avec 
        gauche et droit comme fils."""
        self.etiquette = etiquette
        self.gauche = gauche
        self.droit = droit
 
 
def parcours(arbre, liste):
    """parcours récursivement l'arbre en ajoutant les étiquettes
    de ses noeuds à la liste passée en argument en ordre infixe."""
    if arbre != None:
        parcours(arbre.gauche, liste)
        liste.append(arbre.etiquette)
        parcours(arbre.droit, liste)
 
 
 
def insere(arbre, cle):
    """insere la cle dans l'arbre binaire de recherche représenté par arbre.
    Renvoie l'arbre modifié."""
 
    if arbre == None:
        return Noeud(cle, None, None) # creation d'une feuille
    else:
        if cle < arbre.etiquette:
            arbre.gauche = insere(arbre.gauche, cle)
        else:
            arbre.droit = insere(arbre.droit, cle)
        return arbre
 
if __name__ == "__main__":
    n7 = Noeud(7, None, None)
    n3 = Noeud(3, None, None)
    n2 = Noeud(2, None, n3)
    n5 = Noeud(5, n2,   n7)
    t1 = []
    parcours(n5, t1)
    n5 = insere(n5, 1)
    n5 = insere(n5, 4)
    n5 = insere(n5, 6)
    n5 = insere(n5, 8)
    t2 = []
    parcours(n5, t2)
    print(t1)
    print(t2)

2 - Tuple

⇩ ⇧ ⤊

Puisqu'un arbre est un triplet (g,v,d), on peut utiliser le type tuple pour les implémenter.

On obtient alors un type immuable bien entendu.

05° Dans cet exercice, on considère des arbres binaires de recherche qui sont :

soit l’arbre vide identifié par None ;
soit un nœud, contenant une clé et deux sous-arbres gauche et droit et représenté par un triplet (g, v, d) où g et d sont les sous-arbres gauche et droite et v la clé.

L'arbre binaire de recherche abr1 ci-dessus est créé par le code python suivant :

>>> n0 = (None, 0, None) >>> n3 = (None, 3, None) >>> n2 = (None, 2, n3) >>> abr1 = (n0, 1, n2) >>> abr1 ((None, 0, None), 1, (None, 2, (None, 3, None)))

Écrire une fonction récursive insertion_abr(a, cle) qui prend en paramètres une clé cle et un arbre binaire de recherche a , et qui renvoie un arbre binaire de recherche dans lequel cle a été insérée.
Dans le cas où cle est déjà présente dans a, la fonction renvoie l’arbre a inchangé. On ne gère donc pas ici les valeurs identiques multiples.

Résultats à obtenir :

>>> insertion_abr(abr1, 4) ((None,0,None),1,(None,2,(None,3,(None,4,None)))) >>> insertion_abr(abr1, -5) (((None,-5,None),0,None),1,(None,2,(None,3,None))) >>> insertion_abr(abr1, 2) ((None,0,None),1,(None,2,(None,3,None)))

Correction ?

...CORRECTION...

"""
AB NON VIDE : tuple (g, v, d)
AB     VIDE : None
On ne distingue donc pas l'AB NON VIDE de son Noeud-racine.
 
"""
 
def insertion_abr(a:'AB NON VIDE', cle:'Element') -> 'AB NON VIDE':
 
    if cle < a[1]:         # si la clé est plus petite que l'étiquette de l'arbre
        if a[0] is None:   # si l'emplacement à gauche est disponible
            nouvel_arbre = (None, cle, None)          # on crée une feuille
        else:
            nouvel_arbre = insertion_abr( a[0], cle)  # on crée récursivement l'arbre
        return ( nouvel_arbre, a[1], a[2] )
 
    elif cle > a[1]:      # sinon, si la clé est plus grande
        if a[2] is None:  # si l'emplacement droite est disponible
            nouvel_arbre = (None, cle, None)          # on crée une feuille
        else:
            nouvel_arbre = insertion_abr( a[2], cle)  # on crée récursivement l'arbre
        return ( a[0], a[1], nouvel_arbre)
 
    else:
        return a    # on renvoie l'arbre inchangé
 
if __name__ == "__main__":
    n0 = (None, 0, None)
    n3 = (None, 3, None)
    n2 = (None, 2, n3)
    abr1 = (n0, 1, n2)
    print(insertion_abr(abr1, 4))
    print(insertion_abr(abr1, -5))
    print(insertion_abr(abr1, 2))

06° Un arbre binaire est soit vide, représenté en Python par la valeur None, soit un nœud représenté par un triplet (g, x, d) où x est l’étiquette du nœud et g et d sont les sous- arbres gauche et droite.

On souhaite écrire une fonction parcours_largeur() qui prend en paramètre un arbre binaire et qui renvoie la liste des étiquettes des nœuds de l’arbre parcourus en largeur.

Remarques

Pour la File, faire soit une File du pauvre (avec du append(x) constant et pop(0) linéaire) ou importer collections et son type deque (avec du append(x) constant et popleft() constant).
Attention à bien lire le sujet : on doit renvoyer un tableau des noeuds rencontrés, pas juste réaliser un affichage.

Exemples :


>>> arbre = ( ( (None, 1, None), 2, (None, 3, None) ), 4, ( (None, 5, None), 6, (None, 7, None) ) )
>>> parcours_largeur(arbre)
[4, 2, 6, 1, 3, 5, 7]

Correction ?

...CORRECTION...

"""
AB NON VIDE : tuple (g, v, d)
AB     VIDE : None
On ne distingue donc pas l'AB NON VIDE de son Noeud-racine.
 
"""
 
def parcours_largeur(ab:'AB') -> list:
    """Renvoie la liste des clés rencontrées"""
 
    # Implémentation avec une mauvaise file, on utilse pop(0)
    t = []  # on crée le tableau des étiquettes rencontrées
 
    if ab is not None:     # ou    if not(a is None):
        f = []  # on crée une file
        f.append(ab)
        while f != []:
            ab = f.pop(0)      # on défile l'arbre
            t.append( ab[1] )  # on rajoute sa clé dans le tableau
            if ab[0] is not None:  # si le sous-arbre gauche n'est pas vide
                f.append(ab[0])
            if ab[2] is not None:  # si le sous-arbre droite n'est pas vide
                f.append(ab[2])
    return t
 
 
if __name__ == "__main__":
    arbre = ( ( (None, 1, None), 2, (None, 3, None) ), 4, ( (None, 5, None), 6, (None, 7, None) ) )
    t = parcours_largeur(arbre)
    print(t)

3 - Dictionnaire et tableau

⇩ ⇧ ⤊

07° Dans cet exercice, un arbre binaire de caractères non vide est stocké sous la forme d’un dictionnaire où les clefs sont les caractères des nœuds de l’arbre et les valeurs, pour chaque clef, la liste des caractères des fils gauche et droit du nœud. On utilise la valeur '' pour représenter un fils vide.

Exemple


>>> a = {
 'F':['B','G'],
 'B':['A','D'],
 'A':['',''],
 'D':['C','E'], 
 'C':['',''],
 'E':['',''],
 'G':['','I'],
 'I':['','H'],
 'H':['','']
}

Écrire une fonction récursive taille() prenant en paramètres un arbre binaire arbre NON VIDE sous la forme d’un dictionnaire et un caractère lettre qui est la valeur du sommet de l’arbre, et qui renvoie la taille de l’arbre à savoir le nombre total de nœuds.

On observe que, par exemple, arbre[lettre][0], respectivement arbre[lettre][1], permet d’atteindre la clé du sous-arbre gauche, respectivement droite, de l’arbre de sommet lettre.

Exemples :


>>> taille(a, 'F')
9
 
>>> taille(a, 'B')
5
 
>>> taille(a, 'I')
2

Correction ?

...CORRECTION...

"""
AB NON VIDE : { 'A': ['', ''] } pour représenter une feuille par exemple
 
"""
 
def taille(ab:'AB NON VIDE', cle:'str') -> int:
    """Renvoie la taille de l'arbre binaire NON VIDE dont on donne la clé de la racine"""
 
    if cle == '':  # pas de clé donc il n'y a pas de noeud
        return 0
 
    else:
        return 1 + taille(ab, ab[cle][0]) + taille(ab, ab[cle][1])
 
 
if __name__ == "__main__":
    a = {
     'F':['B','G'],
     'B':['A','D'],
     'A':['',''],
     'D':['C','E'], 
     'C':['',''],
     'E':['',''],
     'G':['','I'],
     'I':['','H'],
     'H':['','']
    }
    print(taille(a, 'F'))

4 - Tableau

⇩ ⇧ ⤊

Comment faire pour trouver facilement le fils gauche du fils gauche ? Le père du père d'un noeud ?

Avec l'arbre binaire de recherche, nous avons un moyen assez simple de localiser un noeud par rapport à sa clé.

Mais il existe également un moyen permettant d'identifier les Noeuds d'un Arbre Binaire : leur associer un nombre ... binaire.

4.1 Numérotation binaire des noeuds

Voir

Principe

On peut donner le numéro 1 à la Racine de l'AB.

Le Noeud-Racine d'un sous-arbre gauche porte le numéro de sa mère suivie d'un 0.

Le Noeud-Racine d'un sous-arbre droite porte le numéro de sa mère suivie d'un 1.

Exemple :

La racine est 1 (1 en décimal).
Le Noeud-Racine du sous-arbre gauche porte le numéro 10 (2 en décimal).
Le Noeud-Racine du sous-arbre droite porte le numéro 11 (3 en décimal).

Nombre de bits et nombre d'étages

Quelque soit la convention pour profondeur et hauteur, on voit que le nombre d'étages donne le nombre de bits des noeuds les plus profonds.

Ici, trois étages : trois bits au maximum.

Dans les questions ci-dessous, on prendra la convention d'une profondeur 0 pour la racine.

08° En utilisant cette notation, combien peut-on avoir de noeuds (au maximum) dans un AB de hauteur 2 ?

Correction ?

...CORRECTION...

Hauteur 2 avec cette convention veut dire qu'on a 3 étages (0, 1 et 2).

3 étages donc les noeuds les plus bas ont un numéro à 3 bits xxx .

On a donc 2³ - 1 = 7 noeuds différents (de 1 à 7).

09° Combien peut-on avoir de noeuds, au maximum, dans un AB de hauteur 7 ?

Correction ?

...CORRECTION...

Hauteur 7, étages de 0 à 7, donc 8 étages.

8 étages donc les noeuds les plus bas ont un numéro à 8 bits xxxx xxxx .

On a donc 2⁸ - 1 = 255 noeuds différents (de 1 à 255).

10° Sur l'arbre proposé, rajouter les deux prochains noeuds en utilisant le système de numérotation proposé.

Correction ?

...CORRECTION...

Numérotation Binaire avec deux noeuds supplémentaires

11° Avec ce système binaire, comment trouver facilement les numéros des deux fils du noeud 14₁₀ ou 1110 ₂ ?

Correction ?

...CORRECTION...

En binaire, 14 se note 8+4+2 soit 1110 .

Le fils gauche est donc 1110 0 , soit 16+8+4 = 28.

Le fils droite est donc 1110 1 , soit 16+8+4+1 = 29.

Les enfants du noeud 14 sont donc les noeuds 28 et 29.

12° Avec ce système binaire, par quel numéro est identifié le père du père du noeud 65 ?

Correction ?

...CORRECTION...

En binaire, 65 se note 64+1 soit
1000001

Pour trouver le père, il suffit de supprimer le 1 de droite :

100000

Pour trouver le père du père, il suffit de supprimer encore le chiffre 0 de droite :

10000

Le père du père du noeud numéro 65 est donc le numéro 16.

On a donc simplement trouver le père du père en divisant deux fois par deux (en division euclidienne).

4.2 Implémentation d'un Arbre via un tableau

Voir

On peut utiliser ce système pour stocker notre Arbre Binaire dans un tableau.

La Racine possède l'indice 1.

Le fils-gauche d'un noeud d'indice i possède l'indice 2*i.

Le fils-droite d'un noeud d'indice i possède l'indice 2*i+1.

Le père d'un noeud d'indice i possède l'indice i//2.

13° Avec ce système décimal, par quel numéro est identifié le père du père du noeud 40 ?

Correction ?

...CORRECTION...

Il suffit de diviser deux fois par 2.

Le père du noeud 40 est le noeud 20.

Le père du noeud 20 est le noeud numéroté 10.

14° Avec ce système décimal, par quel numéro est identifié le fils-droite du fils-gauche du noeud d'indice 5 ?

Correction ?

...CORRECTION...

On multiplie par 2 pour trouver le fils-gauche ! 2*5 = 10.

On multiplie par 2 et on rajoute 1 pour trouver le fils-droite : 10*2+1

Le noeud numéro 21 est donc le fils-droite du fils-gauche du noeud 5.

15° Avec ce système décimal, par quel numéro est identifié le fils-gauche du fils-droite du noeud d'indice 5 ?

Correction ?

...CORRECTION...

On multiplie par 2 et on rajoute 1 pour trouver le fils droite ! 2*5+1 = 11.

On multiplie par 2 pour trouver le fils gauche : 11*2

Le noeud numéro 22 est donc le fils-droite du fils-gauche du noeud 5.

16° Fournir l'implémentation de cet Arbre Binaire sous forme d'un tableau :

Correction ?

...CORRECTION...

17° Quel est l'indice de la case qui stockera le fils-droite du noeud D :

Correction ?

...CORRECTION...

Le noeud D possède l'indice 14.

On calcule donc 14*2+1, soit 29.

4.3 Localisation des parents et enfants

Voir

Pour trouver le fils-gauche du fils-droite du fils-gauche du nombre 101 ou 5 en décimal

Méthode 1 : on travaille en binaire

on part de 101,
on atteint le fils-gauche 1010 ,
puis le fils-droite 10101
puis le fils-gauche 101010 .

Méthode 2 : on travaille en décimal

on part de 5,
on atteint le fils-gauche 10,
puis le fils-droite 21
puis le fils-gauche 42.

Avec une telle implémentation, on peut atteindre un noeud connu à temps constant.

Par contre, la recherche d'un élément de position inconnu reste à coût linéaire par rapport à la taille de l'arbre...

5 -

⇩ ⇧ ⤊

Activité publiée le 02 01 2021
Dernière modification : 02 02 2025
Auteur : ows. h.

⏪

⏫

⏩