précédent | suivant | table des matières

Les arbres de décision.

Un arbre de décision est un arbre binaire ordonné dans lequel :

Chaque noeud interne est étiqueté avec une comparaison.
Chaque feuille est étiquetée avec une permutation ordonnée des éléments.

Les branches gauches de l'arbre de décision correspondent à la réponse oui et les branches droites à la réponse non.

Un parcours de l'arbre dans ce cas consiste à poser la question qui est étiquette du noeud, et à aller à gauche ou à droite suivant la réponse à la question. Une feuille est aussi appelée verdict.

Un arbre de décision est valide pour trier un ensemble à n éléments s'il associe à toute relation d'ordre entre ces éléments un verdict compatible avec cette relation.

Un arbre de décision est élagué si aucun parcours n'est contradictoire, c'est à dire que toutes ses feuilles sont accessibles à partir de la racine par une suite consistante de questions.

Exemple :

Tout algorithme de tri par comparaisons correspond à un arbre de décision. L'arbre de décision àgauche correspond à l'algorithme de tri suivant :

if (A<B)
   if (B<C)
           T = A,B,C;
   else
      if (A<C)
           T = A,C,B
      else T = C,A,B
else
   if (B<C)
      if (A<C)
           T = B,A,C
      else T = B,C,A
   else    T = C,B,A

L'arbre de décision à gauche correspond à l'algorithme de tri par insertion de trois éléments.

haut de la page