Skip to content

NSI - Terminale - Les arbres binaires

Arbres binaires et algorithmes

Cliquez sur le lien du chapitre de cours à consulter:

Définitions

Un arbre binaire est une des formes existantes de structures arborescentes. Dans ce cas particulier, chaque position appelée nœud ouvre sur deux branches appelées sous-arbre de gauche et sous-arbre de droite. C’est un arbre de degré 2 ( un nœud a maximum 2 enfants). Chaque nœud peut rejoindre un autre nœud qui continuera lui même avec deux branches. Lorsqu’un nœud a ses deux branches vides, on l’appelle une feuille. Chaque nœud a un parent, sauf un nœud que l’on appelle la racine. La laison entre un deux noeuds est appelée une arête ou une branche

Taille d’un arbre: la taille d’un arbre est égale au nombre de nœuds de l’arbre. Ci-dessus l’arbre est de taille 4.

Profondeur d’un nœud ( ou niveau d’un nœud) est sa distance à la racine (nombre d’arêtes qu’il faut parcourir à partir de la racine pour aller jusqu’au nœud en question).

Hauteur d’un arbre: un arbre est vide lorsqu’il ne contient aucun nœud. Un arbre vide a une hauteur 0. Un arbre non vide a une hauteur qui dépend de la profondeur de sa racine, si on l'a choisie égale à 1, la hauteur de l’arbre sera le nombre de nœuds rencontrés en descendant de la racine jusqu’au nœud le plus profond . Ci-dessus nous avons ainsi un arbre binaire de hauteur 3.

↑ Retour en haut

Mesures

Relation entre le nombre de noeuds et sa hauteur: si N désigne la taille d’un arbre ( son nombre de nœuds) et h sa hauteur, pour un arbre binaire de racine à la profondeur 1, on a l’inégalité suivante: h ≤ N ≤ 2h-1

Code python de mesure de la taille et de la hauteur: 

# classe qui permet de construire des arbres
class Nœud:
    def __init__(self, g,v,d):
            self.gauche = g
            self.valeur = v
            self.droite = d

# fonctions de mesures
def taille(arbre):
    """ nombre de noeuds de l'arbre"""
    if arbre is None:
        return 0
    else:
        return 1 + taille(arbre.gauche) + taille(arbre.droite)
def hauteur(arbre):
            """ hauteur de l'arbre"""
            if arbre is None:
                return 0
            else:
                return 1 + max(hauteur(arbre.gauche), hauteur(arbre.droite))

# Exemple du codage d'un arbre avec ce modèle objet:
nœud_D = Noeud(None,'D',None)
nœud_c = Noeud(None,'C',None)
noeud_b = Noeud(None,'B',nœud_c)
arbre = Noeud(noeud_b,'A',nœud_D)

Algorithmes de parcours

Il y a plusieurs façons de parcourir un arbre pour extraire la valeur des noeuds, on distingue les parcours en profondeur appelées infixe, préfixe, postfixe (suffixe) et le parcours en largeur, vous trouverez ci-dessous le principe et le code python de chacun de ces parcours pour l'arbre suivant:

  • Parcours en profondeur infixe

On affiche la valeur du nœud la deuxième fois qu’il est rencontré ci ce dernier à un fils à gauche ou dés la première rencontre s’il n’a pas de fils à gauche, on privilégie d'abord la visite du sous-arbre gauche, pour l’arbre ci-dessus cela donnera : 4,2,7,5,8,1,3,9,6. Le code est basé sur une fonction récursive: 

def parcours_infixe(arbre):
    if arbre is None:
        return
    parcours_infixe(arbre.gauche)
    print(arbre.valeur)
    parcours_infixe(arbre.droite)
  • Parcours en profondeur prefixe

Dans ce cas de parcours, on liste la valeur de chaque noeud la première fois qu’on la rencontre et on privilégie d'abord la visite du sous-arbre gauche d'un noeud. Cela donne l'affichage: 124578369 pour l'arbre étudié. Implémentation:

def parcours_prefixe(arbre):
    if arbre is None:
        return
    print(arbre.valeur)
    parcours_prefixe(arbre.gauche)
    parcours_prefixe(arbre.droite)
  • Parcours en profondeur postfixe

Dans ce cas de parcours en profondeur, on liste la valeur de chaque noeud la dernière fois qu’on la rencontre dans le parcours et on privilégie d'abord la visite du sous-arbre gauche d'un noeud. Cela donne l'affichage: 478529631 pour l'arbre étudié. Implémentation:

def parcours_postfixe(arbre):
    if arbre is None:
        return
    parcours_postfixe(arbre.gauche)
    parcours_postfixe(arbre.droite)
    print(arbre.valeur)
  • parcours en largeur

Le parcours d’un arbre en largeur consiste à partir de la racine puis visiter son enfant gauche puis le enfant droit, puis l'enfant gauche du l'enfant gauche de la racine, puis l'enfant droit de l'enfant droit de la racine, puis leurs enfants, etc.. Cela donne l'affichage: 123456789 pour l'arbre étudié.

Implémentation:

La mise en œuvre du code est moins simple. On peut utiliser une file, On met l’arbre à parcourir dans la file f, tant que la file n’est pas vide: on enlève un element de la file (un objet noeud), si l'élément enlevé ne vaut pas None, on affiche la valeur du nœud, on met dans la file son enfant gauche puis on met dans la file son enfant droit et on recommence tant que la file n’est pas vide. Ci dessous, le code suppose que vous disposez d'une classe file avec les méthodes est_vide(), retirer() et ajouter(): 

 # classe qui permet de construire des arbres
class Nœud:
    def __init__(self, g,v,d):
        self.gauche = g
        self.valeur = v
        self.droite = d

# classe qui permet de créer un objet file
class Ma_file:
    def __init__(self):
        self.tete = []
    def est_vide(self):
        return len(self.tete) == 0
    def ajouter(self, valeur):
            self.tete.append(valeur)
    def retirer(self):
        if not self.est_vide():
            valeur = self.tete.pop(0)
            return valeur

def parcours_en_largeur(un_arbre, f):
    ''' la variable f est assignée à un objet de la classe file, 
    et la variable un_arbre est assignée à l'objet qui représente un arbre''' 
    f.ajouter(un_arbre)
    while not f.est_vide():
        arbre = f.retirer()
        if arbre is not None:
            print(arbre.valeur, end= ";")
            f.ajouter(arbre.gauche)
            f.ajouter(arbre.droite)

# création des objets

B = Noeud(None,'9', None)
C = Noeud('6', B, None)
D = Noeud('3', None, C)
E = Noeud(None,'8', None)
F = Noeud(None,'7', None)
G = Noeud ( '5', F, E)
H = Noeud (None,'4', None)
I = Noeud( '2', H, G)
J = Noeud('1', I, D)
f = Ma_file()
# utilisation de la fonction parcours_en_largeur
parcours_en_largeur(J, f)
↑ Retour en haut

Les arbres binaires de recherches (ABR)

Un arbre binaire de recherche appelé ABR est un arbre dont les nœuds contiennent des valeurs qui peuvent être comparées entre elles ( des nombres, des caractères par exemples). Pour tout nœud de l’arbre, toutes les valeurs situées dans son sous-arbre de gauche sont plus petites que lui et toutes les valeurs situées dans son sous-arbre de droite sont plus grandes ou égales à lui.

↑ Retour en haut

Les algorithmes de gestion des ABR (ABR)

Un ABR permet une recherche optimisée, on abandonne le parcours de la sous branche qui ne correspond pas au critère de recherche. Par exemple écrivons une fonction qui indique si un nombre appartient à l’arbre de recherche.

Représentation en python: 

def appartient(nbre, arbre):
    """determine si nbre est dans arbre"""
    if arbre is None:
        return False
    if nbre < arbre.valeur:
        return appartient(nbre, arbre.gauche)
    elif nbre > arbre.valeur:
        return appartient(nbre, arbre.droite)
    else:
        return True

Insertion d'un nouveau noeud dans un abr: 

def ajoute(nbre, arbre):
    """ajoute nbre dans l'arbre de recherche existant 
    et renvoie un nouvel arbre"""
    if arbre is None:
        return Noeud( None, nbre, None)
    if nbre < arbre.valeur:
        return Noeud( ajoute(nbre, arbre.gauche), arbre.valeur, arbre.droite)
    else:
        return Noeud(arbre.gauche, arbre.valeur, ajoute(nbre, arbre.droite))

↑ Retour en haut

La complexité en temps

La complexité en temps représente une estimation de la relation entre le temps d'exécution t d'un algorithme et le nombre N données qu'il doit traiter si on se place dans le pire des cas. Par exemple si on considère un algorithme qui parcourt une liste des N éléments avec une boucle for, le pire des cas est de vouloir atteindre le dernier élément de cette liste, la complexité en temps va être une estimation de la relation entre le temps d'exécution de l'algorithme pour atteindre la dernière donnée en fonction du nombre de données N à parcourir. On se poser la question, comment va évoluer le temps d'exécution si je double le nombre de données à parcourir.
La complexité se note O(..) avec entre parenthèses la relation estimée entre le temps d'exécution et le nombre de données N; dans l'exemple précédent du parcours d'une liste, le temps de parcours avec une boucle for est directement proportionnel au nombre d'éléments N, on dit que la complexité en temps est en O(N) (temps d'exécution proportionnel à N) .

Pour ceux qui ont besoin de concret: s'il faut t = 1s pour parcourir une donnée, il faudra t = 10s pour atteindre le dernier élément d'une liste de N = 10 éléments, si je double le nombre de données dans la liste (N = 20), il faudra alors 20s pour atteindre le dernier élément. On voit que le temps t de parcours est directement proportionnel au nombre N d'éléments.

Voici les compléxités souvent rencontrées en informatique:

Voici l'estimation de la complexité pour un arbre binaire de recherche de hauteur h et de taille N, si on considère la racine à la hauteur 1, le pire des cas est la recherche d'un élément qui est dans une feuille de l'ABR:

↑ Retour en haut