TD d’algorithmique avancée

Ce document présente un ensemble d'exercices et de notions avancées en algorithmique, centrés sur le dénombrement dans les arbres binaires, la complexité des algorithmes de tri par comparaison via les arbres de décision, ainsi que les arbres binaires de recherche. Il s'adresse aux étudiants en informatique souhaitant approfondir leur compréhension des structures d'arbres et de leur impact sur les algorithmes.

Dénombrement sur les arbres binaires

On considère un arbre binaire non vide avec n nœuds, f feuilles et une hauteur h.

Hauteur maximale d’un arbre à n nœuds

La hauteur maximale d’un arbre binaire à n nœuds est atteinte lorsque l’arbre est dégénéré, c’est-à-dire que chaque nœud n’a qu’un seul fils. Dans ce cas, la hauteur maximale est :

hauteur maximale = n - 1

Nombre maximal de feuilles d’un arbre de hauteur h

Le nombre maximal de feuilles d’un arbre binaire de hauteur h est atteint lorsque l’arbre est complet, c’est-à-dire que tous les niveaux sont remplis sauf peut-être le dernier. Le nombre maximal de feuilles est alors :

nombre maximal de feuilles = 2^h

Nombre maximal de nœuds d’un arbre de hauteur h

Le nombre maximal de nœuds d’un arbre binaire de hauteur h correspond à un arbre complet, donné par :

nombre maximal de nœuds = 2^(h+1) - 1

Hauteur minimale d’un arbre à n nœuds

La hauteur minimale d’un arbre binaire à n nœuds est celle d’un arbre parfaitement équilibré, où les nœuds sont répartis de manière optimale sur les niveaux. Elle est donnée par :

hauteur minimale = ⌊log₂(n)⌋

Nombre de branches vides dans un arbre à n nœuds

On appelle branches vides les fils gauches ou droits absents (vides) dans l’arbre. Le nombre total de branches vides dans un arbre binaire à n nœuds est :

nombre de branches vides = n + 1

Indication : On distingue les nœuds selon qu’ils ont zéro, un ou deux fils, et on compte les branches vides en conséquence.

Nombre maximal de feuilles si chaque nœud a zéro ou deux fils

Si chaque nœud est soit une feuille (degré 0), soit a deux fils (degré 2), alors le nombre de feuilles f satisfait :

f ≤ (n + 1) / 2

Il y a égalité si et seulement si cette condition est respectée pour tous les nœuds.

Relation entre nombre de feuilles et nœuds de degré deux

Le nombre de feuilles d’un arbre binaire est égal au nombre de nœuds de degré deux plus un :

f = nombre de nœuds de degré deux + 1

Complexité du tri par comparaison et arbres de décision

Les algorithmes de tri par comparaison peuvent être modélisés par des arbres de décision. Chaque nœud interne de l’arbre correspond à une comparaison entre deux éléments, et chaque feuille correspond à une permutation ordonnée des éléments.

Soient a₁, a₂, ..., aₙ les n valeurs à trier. Chaque nœud interne est étiqueté par une comparaison aᵢ ≤ aⱼ. L’exécution du tri suit un chemin depuis la racine jusqu’à une feuille, en fonction des résultats des comparaisons.

Exemple : arbre de décision pour le tri par insertion de 3 éléments

                 a2 ≤ a3
                /       \
           a1 ≤ a2       a1 ≤ a3
          /      \       /      \
(1,2,3)   (2,1,3)  (1,3,2)   a2 ≤ a3
                              /     \
                         (3,1,2)  (2,3,1)
                                    \
                                   (3,2,1)

Nombre de feuilles de l’arbre de décision

Le nombre de feuilles correspond au nombre de permutations possibles des n éléments, soit n! (factorielle de n).

Borne inférieure sur la hauteur de l’arbre de décision

La hauteur h de l’arbre de décision satisfait :

2^h ≥ n!

En prenant le logarithme en base 2 :

h ≥ log₂(n!)

En utilisant la formule de Stirling, on a :

n! > (n / e)^n

d’où :

h = Ω(n log n)

Borne inférieure sur la complexité du tri

La complexité temporelle minimale des algorithmes de tri par comparaison est donc :

Ω(n log n)

Arbres binaires de recherche (ABR)

Temps de création d’un ABR à partir d’une liste quelconque

Le temps de création d’un arbre binaire de recherche à partir d’une liste de n éléments est au minimum :

Ω(n log n)

Ce résultat découle du fait que chaque insertion dans un ABR équilibré prend en moyenne un temps logarithmique, et il faut insérer n éléments.

Algorithme pour tester si un arbre est un ABR

fonction estABR(noeud, min, max) :
    si noeud est nul :
        retourner vrai
    si noeud.valeur ≤ min ou noeud.valeur ≥ max :
        retourner faux
    retourner estABR(noeud.fils_gauche, min, noeud.valeur) ET
           estABR(noeud.fils_droit, noeud.valeur, max)

Ce test vérifie récursivement que pour chaque nœud, toutes les valeurs du sous-arbre gauche sont strictement inférieures à la valeur du nœud, et celles du sous-arbre droit strictement supérieures.

Glossaire des termes clés

• Arbre binaire : Structure de données où chaque nœud a au plus deux fils, appelés fils gauche et fils droit.
• Hauteur d’un arbre : Longueur du plus long chemin entre la racine et une feuille.
• Feuille : Nœud sans fils (degré 0).
• Branches vides : Fils gauche ou droit absents d’un nœud.
• Arbre binaire de recherche (ABR) : Arbre binaire où pour chaque nœud, les valeurs du sous-arbre gauche sont inférieures, et celles du sous-arbre droit supérieures à la valeur du nœud.
• Arbre de décision : Arbre représentant les comparaisons effectuées par un algorithme de tri.
• Complexité Ω(n log n) : Borne inférieure asymptotique indiquant que l’algorithme ne peut pas être plus rapide que proportionnel à n log n.
• Formule de Stirling : Approximation de la factorielle n! utilisée pour estimer la croissance des permutations.

Points clés à retenir

• La hauteur maximale d’un arbre binaire à n nœuds est n - 1, la minimale est ⌊log₂(n)⌋.
• Le nombre maximal de feuilles dans un arbre de hauteur h est 2^h, et le nombre maximal de nœuds est 2^(h+1) - 1.
• Le nombre de branches vides dans un arbre binaire à n nœuds est toujours n + 1.
• Le nombre de feuilles est égal au nombre de nœuds de degré deux plus un, si chaque nœud a zéro ou deux fils.
• Les arbres de décision pour les tris par comparaison ont n! feuilles, ce qui impose une hauteur minimale Ω(n log n).
• La complexité minimale des algorithmes de tri par comparaison est donc Ω(n log n).
• La création d’un arbre binaire de recherche à partir d’une liste quelconque nécessite au minimum Ω(n log n) opérations.
• Un test récursif basé sur des bornes min et max permet de vérifier si un arbre est un ABR.