Définitions

Un arbre est une structure de données hiérarchique, généralement dynamique. Il peut être considéré comme une liste chaînée non linéaire de maillons ( ou nœuds ). Ces derniers forment un graphe orienté o� chaque nœud a au plus 1 prédécesseur et n successeurs (n >= 0 ).

Si le nombre de successeurs de tout nœud est au plus égal à 2, l'arbre est dit binaire. Si ce nombre est au plus égal à 3, l'arbre est dit ternaire. Et ainsi de suite. . .

Et d'une façon générale, si le nombre de successeurs est au plus égal à n, l'arbre est dit arbre m-aire d'ordre n.

Terminologie

Sur les arbres on définit les termes suivants :

Racine : C'est le nœud qui n'a pas de prédécesseur. La racine constitue la caractéristique d'un arbre.

Feuille : c'est le nœud qui n'a pas de successeur. Une feuille est aussi appelée un nœud externe.

Nœud interne : c'est tout nœud qui admet au moins un successeur.

Fils d'un nœud : ce sont ses successeurs.

Frères : ce sont les successeurs issus d'un même nœud.

Père : c'est un nœud qui admet au moins un successeur.

Sous arbre : C'est une portion de l'arbre.

Descendants d'un nœud : ce sont tous les nœuds du sous arbre de racine nœud.

Ascendants d'un nœud : ce sont tous les nœuds se trouvant sur la branche de la racine vers ce nœud.

Branche : Les ascendants d'une feuille constituent une branche de l'arbre.

Degré d'un nœud : C'est le nombre de ses fils.

Niveau d'un nœud : On dit que la racine a le niveau 0, ses fils ont le niveau 1, les fils des fils ont le niveau 2. Etc.

Profondeur de l'arbre : C'est le niveau maximal des feuilles de l'arbre.

Forêt : C'est un ensemble d'arbres.

En plus des termes définis dans la section précédente, on définit d'autres termes sur les arbres binaires. En particulier, on parlera de fils gauche et fils droit, de sous arbre gauche et sous arbre droit d'un nœud donné de l'arbre.

un arbre est dit strictement binaire si chaque nœud qui n'est pas une feuille a exactement deux fils. Si un arbre strictement binaire a n feuilles, le nombre total de ses nœuds est 2n-1. Le nombre de ses nœuds non feuilles ( nœuds internes ) est par conséquent égal à n-1.

C'est un arbre strictement binaire o� toutes les feuilles sont au même niveau. Dans un arbre binaire complet de profondeur d, le nombre de nœuds est

n = 20 + 21 +22 + . . . 2d = 2d+1 - 1

Donc 2d nœuds feuilles et 2d-1 nœuds non feuilles

Inversement, connaissant le nombre de nœuds n d'un arbre binaire complet, sa profondeur est Log₂ (n+1) - 1.

Modèle sur les arbres binaires

Sur les arbres binaires, on définit le modèle(machine abstraite) suivant:

Un arbre est défini par son nœud racine.

Si p référence un nœud, Info(p), Fg(p), Fd(p) permettent d'accéder à l'information, au fils gauche et au fils droit du nœud p respectivement.

Si p référence un nœud, Aff-info(p, x), Aff-fg(p, x), Aff-fd(p, x) permettent de modifier l'information, le fils gauche et le fils droit du nœud p respectivement.

La fonction Creernœud(x) crée un nœud avec x comme information et retourne la référence du nœud. Le nœud créé a Nil comme fils gauche et droit.

La fonction Liberernœud(p) libère le nœud référencé par p.

Parcours des arbres binaires

Une trentaine d'ordres de parcours ont été recensés sur les arbres binaires. Cependant, les trois ordres suivants sont les plus utilisés :

Préordre : n T1 T2

Inordre : T1 n T2

Postordre : T1 T2 n

n désigne la racine d'un arbre binaire, T1 et T2 ses sous arbres gauche et droit.

Arbre de recherche binaire

C 'est une structure de données de base utilisée pour représenter des ensembles dont les éléments sont ordonnés par une relation d'ordre notée < (au sens strict). Un arbre de recherche binaire est un arbre dont les nœuds renferment les éléments d'un ensemble ordonné. La propriété la plus importante est que tous les éléments stockés dans le sous arbre gauche d'un nœud contenant x sont strictement inférieurs à x, et tous les éléments rangés dans le sous arbre droit d'un nœud contenant x sont strictement supérieurs à x.

Le parcours en inordre d'un arbre de recherche binaire donne la liste ordonnée de tous ses éléments.

La recherche dans un arbre de recherche binaire est dichotomique. A chaque étape, un sous arbre est éliminé. D'o� l’appellation de l'arbre.

L'insertion d'un élément se fait toujours au niveau d'une feuille ou à gauche (droite) d'un nœud ne possédant pas de fils gauche (droit). En d'autres termes, l'élément inséré est toujours une feuille.

La suppression est plus délicate. Nous rappelons dans ce qui suit les différents cas de suppression d'un élément et les actions à entreprendre pour chaque cas.

Soit n le pointeur de l'élément qu'on veut supprimer.

n                

fg                  fd                                  Action

a) NIL          NIL                               Remplacer n par NIL

b) NIL         #NIL                              Remplacer n par Fd(n)

c) #NIL     NIL                                 Remplacer n par Fg(n)

d) #NIL     #NIL                              1. Rechercher le plus petit descendant du sous-arbre droit, soit p.

                                                        2. Remplacer Info(n) par Info(p)

                                                        3. Remplacer p par Fd(p)

Applications des arbres binaires

Un arbre binaire est utile quand une décision sur deux doit être prise à chaque étape d'un traitement. Nous donnons, dans ce qui suit, quatre applications des arbres de recherche binaire.

Trouver tous les doubles dans une liste de nombres

On veut déterminer les doubles dans une suite de nombres se trouvant sur une machine-nombre o� chaque ordre de lecture délivre le prochain nombre.

A un moment donné, pour savoir si un nombre venant d'être lu est double ou pas, il faut examiner tous les éléments déjà lus. Plusieurs structures sont possibles pour ranger ces derniers. Que l'on prenne un tableau ou une liste linéaire chaînée, qu'on les maintienne ordonnés ou pas, l'inconvénient réside toujours dans la recherche et/ou l'insertion des éléments. Par contre, l'utilisation d'un arbre de recherche binaire pour cette application simple permet un gain considérable de temps indépendamment de l'opération.

Représentation des expressions arithmétiques

Une expression arithmétique peut être représentée par un arbre strictement binaire o� les opérandes sont au niveau des feuilles et les nœuds non feuilles sont des opérateurs.

Le parcours en préordre donne la forme polonaise préfixée, le postordre la forme postfixée et l'inordre la forme infixée (forme normale sans parenthèses)

Représentation des listes par des arbres binaires

On peut représenter une liste linéaire chaînée par un arbre binaire de la façon suivante : Les éléments de la liste sont au niveau des feuilles. Chaque nœud qui n'est pas une feuille contient le nombre de feuilles de son sous arbre gauche.

La représentation d'une liste linéaire chaînée en un arbre binaire répond avec efficacité au problème de la recherche du k-ième élément et à la suppression d'un élément donné.

Code de Huffman

Soit à coder un message composé de suites de caractères qui apparaissent avec des probabilités connues. Nous voulons coder chaque caractère en une séquence de 0 et de 1 de telle sorte qu'aucun code n'est le préfixe d'un autre code ( ne commence par un autre code ). Gr�ce à cette propriété dite propriété du préfixe, on peut décoder une suite de bits en répétant des suppressions de chaînes.

L'algorithme part d'une forêt. Chaque arbre de celle-ci est associé à un caractère à coder.

L'algorithme de Huffman consiste à répéter les deux étapes suivantes tantqu' il reste plus d'un arbre dans la forêt :

- sélectionner deux arbres a et b ayant les plus faibles probabilités.

- remplacer les par un arbre x ayant comme fils a et b. L'arbre x a donc comme probabilité : p(x) = p(a) + p(b)

Les arbres m-aires

Un arbre m-aire d'ordre p est défini de telle sorte que tout nœud a au plus p nœuds. De même que sur les arbres binaires, on peut définir les types de parcours suivants sur les arbres m-aires.

Préordre : n T1 T2 . . . Tp

Inordre : T1 n T2 T3 ...Tp

Postordre : T1 T2 T3 . . . Tp n

n étant la racine de l'arbre et T1, T2, ....Tp ses sous arbres de gauche à droite.

La transformation d'un arbre m-aire en un arbre binaire se fait comme suit :

1. détacher tous les fils qui ne sont pas les plus à gauche et lier les de telle sorte que les frères soient dans une liste linéaire chaînée.

2. faire une rotation des listes linéaires chaînées de 45� dans le sens des aiguilles d'une montre.

Dans la transformation précédente, la racine de l'arbre résultant n'a pas de fils droit. On exploite ce champ en le faisant pointer sur la racine du prochain arbre transformé de la forêt. De même, le fils droit de la racine de l'arbre résultant de cette opération n'a pas de sous arbre droit dans son nœud le plus à droite. Il pointera alors le troisième arbre transformé. Et ainsi de suite...

Transformation d'un arbre binaire en une forêt

Inversement, on peut transformer tout arbre binaire en une forêt.

Représentation des arbres

Il existe plusieurs façons de représenter un arbre:

- statique ( dans un tableau )

- dynamique ( allocation dynamique des nœuds )

- mixte

Une autre façon de ranger un arbre est l'utilisation des représentations séquentielles dans lesquelles on ne représente pas les champs pour les fils. Les éléments de l'arbre sont alors rangés dans un ordre prédéfini.