Algorithmes sur les arbres binaires

⚙️ Chapitre : Algorithmes sur les arbres

1️⃣ Création de la classe

Pour implémenter un arbre binaire, on peut utiliser la POO en utilisant une classe Node:

class Node:
    def __init__(self, val):
        # Attributs de l'objet
        self.val = val
        self.gauche = None
        self.droit = None

• L´étiquette du noeud est définie lors de la création de l'objet avec l'attribut val.
• Les attributs gauche et droit prennent la valeur None par défaut.

La structure d’un arbre permet de représenter des relations de dépendance ou d’organisation.

2️⃣ Instanciation d'un arbre

Pour créer cet arbre, procédons ainsi :

arbre = Node('8') # Instanciation de la racine
# Sous-arbre gauche
arbre.gauche = Node('3')
arbre.gauche.gauche = Node('1')
arbre.gauche.droit = Node('6')
# Sous-arbre droit
arbre.droit= Node('10')
arbre.droit.droit= Node('14')

• Les attributs gauche et droit permettent de construire l'arbre à partir de sa racine.

3️⃣ Parcours en profondeur (DFS)

Le parcours en profondeur qui utilise la récursivité et se fait selon trois méthodes différentes que vous devez connaitre : préfixe, infixe ou suffixe.

Parcours préfixe (preorder) :

def prefixe(arbre):
    # cas de base
    if arbre==None:
        return
    else:
        print(arbre.val,end='→')
        prefixe(arbre.gauche)
        prefixe(arbre.droit)
# appel
prefixe(arbre)

Parcours infixe (inorder) :

def infixe(arbre):
    # cas de base
    if arbre==None:
        return
    else:
        infixe(arbre.gauche)
        print(arbre.val,end='→')
        infixe(arbre.droit)
# appel
infixe(arbre)

• Comme il s'agit d'un arbres binaires de recherche (ABR en français, BST en anglais), le parcours infixe affiche les valeurs des noeuds dans l'ordre croissant.

Parcours postfixe (postorder) :

def postfixe(arbre):
    # cas de base
    if arbre==None:
        return
    else:       
        postixe(arbre.gauche)
        postixe(arbre.droit)
        print(arbre.val,end='→')
# appel
postfixe(arbre)

• On remarque que la position du print par rapport aux appels récursif détermine le type de parcours.

3️⃣ Parcours en largeur

Le parcours en largeur qui consiste à afficher les valeurs des nœuds niveau par niveau, de gauche à droite en commençant par la racine. On utilise pour cela une file pour garder en mémoire le fils gauche et le fils droit du nœud visité jusqu´à ce que la file soit vide.

On ne détaille pas l'algorithme ici mais vous devez le pratiquer. Au bac, un code vous sera fournit, il faut savoir le compléter.

4️⃣ Algorithmes classiques

Hauteur d'un arbre, on utilise la fonction max de Python:

def hauteur(arbre):
    # Cas de base : arbre vide, hauteur 0
    if arbre is None:
        return 0
    # Calcul récursif : 1 + max(hauteur gauche, hauteur droit)
    else:
        return 1 + max(hauteur(arbre.gauche), hauteur(arbre.droit))
print(hauteur(arbre)) # affiche 3

• La hauteur d'un arbre binaire se calcule récursivement en trouvant le chemin le plus long de la racine à une feuille.

Taille d'un arbre (nombre de noeuds), c'est une variante du précédent:

def taille (arbre):
    # Cas de base : arbre vide, pas de noeud
    if arbre == None:
        return 0
    else:
        return 1+taille(arbre.gauche)+taille(arbre.droit)
taille(arbre) # affiche 6

• On incrémente un compteur à chaque visite d'un noeud.

5️⃣ Arbres binaires de recherche

Un arbre binaire de recherche (ABR) est un arbre binaire tel que :

• toutes les valeurs du sous-arbre gauche sont strictement inférieures à la racine ;
• toutes les valeurs du sous-arbre droit sont strictement supérieures à la racine.

Cette propriété permet d’effectuer une recherche efficace d’une valeur.

Principe de la recherche

Pour rechercher une valeur \( x \) :

• si \( x = \) valeur du nœud courant → la recherche est terminée ;
• si \( x < \) valeur du nœud → on continue dans le sous-arbre gauche ;
• si \( x > \) valeur du nœud → on continue dans le sous-arbre droit.

À chaque étape, on élimine la moitié des valeurs possibles.

Complexité

La complexité dépend de la hauteur \( h \) de l’arbre.

Dans le cas général :

Si l’arbre est équilibré, sa hauteur vérifie :

Donc la complexité devient :

En revanche, si l’arbre est dégénéré (chaîne linéaire), alors :

Conclusion

• ABR équilibré → recherche en \( \mathcal{O}(\log n) \)
• ABR dégénéré → recherche en \( \mathcal{O}(n) \)

🔗 Un exercice intéressant, centres étrangers – 2023.
🔗 Cet autre exercice de Polynésie porte sur les arbres binaires, les arbres binaires de recherche, la programmation orientée objet et la récursivité.