Chap. 5 : Arbres - Cours (partie 3)

1. Parcours d’un arbre

Parcourir un arbre signifie visiter tous ses nœuds. Il existe deux grandes catégories de parcours.

1.1. Parcours en Profondeur (DFS)

Dans un parcours en profondeur, on explore complètement une branche avant de passer à la suivante. Comme l’arbre est une structure récursive, ces parcours s’écrivent très naturellement de manière récursive.

Il existe trois ordres principaux selon le moment où l’on traite la racine par rapport à ses fils :

1. Préfixe : Racine, puis Gauche, puis Droit.
2. Infixe : Gauche, puis Racine, puis Droit. (Pour un ABR, cela donne les valeurs triées !)
3. Suffixe (ou Postfixe) : Gauche, puis Droit, puis Racine.

Mise en gardeExemple

Ordre préfixe

Ordre de parcours des sommets : C-Z-U-R-G-Q-H.

Mise en gardeExemple

Ordre infixe

Ordre de parcours des sommets : U-Z-R-G-C-H-Q.

Mise en gardeExemple

Ordre suffixe

Ordre de parcours des sommets : U-G-R-Z-H-Q-C.

Implémentation Python

def parcours_prefixe(arbre):
    if arbre is not None:
        print(arbre.etiquette)  # Traitement de la racine
        parcours_prefixe(arbre.gauche)
        parcours_prefixe(arbre.droit)

def parcours_infixe(arbre):
    if arbre is not None:
        parcours_infixe(arbre.gauche)
        print(arbre.etiquette)  # Traitement de la racine
        parcours_infixe(arbre.droit)

def parcours_suffixe(arbre):
    if arbre is not None:
        parcours_suffixe(arbre.gauche)
        parcours_suffixe(arbre.droit)
        print(arbre.etiquette)  # Traitement de la racine

Mise en gardeExercice

Voici deux arbres binaires. Pour chacun d’entre eux, indiquer l’ordre de parcours des sommets pour chacun de types de parcours en profondeur définis ci-dessus.

1.2. Parcours en Largeur (BFS)

Le parcours en largeur visite les nœuds niveau par niveau : d’abord la racine (niveau 1), puis ses enfants (niveau 2), puis les enfants de ses enfants (niveau 3), etc.

Mise en gardeExemple

Parcours en largeur

Ordre de parcours des sommets : C-Z-Q-U-R-H-G.

Pour implémenter ce parcours, la récursivité n’est pas adaptée. On utilise une structure de File (First In, First Out).

Algorithme

1. Enfiler la racine.
2. Tant que la file n’est pas vide :
   • Défiler un nœud \(N\).
   • Traiter \(N\) (ex: l’afficher).
   • Enfiler le fils gauche de \(N\) (s’il existe).
   • Enfiler le fils droit de \(N\) (s’il existe).

Implémentation Python optimisée

AvertissementAttention à la complexité

Utiliser une liste Python (list) comme une file avec pop(0) est inefficace (complexité \(\mathcal{O}(n)\) pour le décalage des éléments). Il faut utiliser collections.deque qui permet des opérations en \(\mathcal{O}(1)\) aux deux extrémités.

from collections import deque

def parcours_largeur(arbre):
    if arbre is None:
        return
    
    file = deque([arbre])
    
    while file: # Tant que la file n'est pas vide
        noeud = file.popleft() # Défiler (O(1))
        print(noeud.etiquette)
        
        if noeud.gauche is not None:
            file.append(noeud.gauche)
        if noeud.droit is not None:
            file.append(noeud.droit)

2. Algorithmes sur les ABR

2.1. Recherche d’une clé

La recherche dans un ABR exploite la propriété d’ordre : à chaque nœud, on sait si on doit aller à gauche (valeur cherchée plus petite) ou à droite (valeur cherchée plus grande).

def recherche_abr(arbre, valeur) -> bool:
    if arbre is None:
        return False
    if valeur == arbre.etiquette:
        return True
    elif valeur < arbre.etiquette:
        return recherche_abr(arbre.gauche, valeur)
    else:
        return recherche_abr(arbre.droit, valeur)

2.2. Complexité de la recherche

La complexité dépend de la forme de l’arbre, donc de sa hauteur \(h\). À chaque étape, on descend d’un niveau. Le nombre d’étapes maximal est donc \(h\).

• Pire cas (Arbre filiforme) : \(h = n\). La complexité est linéaire \(\mathcal{O}(n)\). C’est le cas si on insère des valeurs déjà triées (1, 2, 3, 4…).
• Meilleur cas (Arbre parfait/équilibré) : \(h \approx \log_2 n\). La complexité est logarithmique \(\mathcal{O}(\log n)\).

C’est pour cela qu’il est important d’avoir des arbres équilibrés.

3. Autres exemples

Exercice 1 : Somme des valeurs

Écrire une fonction récursive qui renvoie la somme de toutes les valeurs d’un arbre d’entiers.

Solution

def somme(arbre):
    if arbre is None:
        return 0
    return arbre.etiquette + somme(arbre.gauche) + somme(arbre.droit)

Exercice 2 : Maximum d’un ABR

Écrire une fonction efficace pour trouver la valeur maximale dans un ABR. (Indice : où se trouve le plus grand élément ?)

Solution

def maximum_abr(arbre):
    if arbre is None:
        return None
    # On va le plus à droite possible
    courant = arbre
    while courant.droit is not None:
        courant = courant.droit
    return courant.etiquette