Cours d'algorithmique : LES ARBRES BINAIRES avec des Exemples

MODELISATION DE LA STRUCTURE

Introduction

Les tableaux sont des structures qui permettent un accès direct à un élément à partir de son indice. Par contre, l'insertion ou la suppression dans de telles structures d'un élément à une position donnée sont des opérations coûteuses. D'un autre côté, les listes chaînées facilitent les actions d'insertion et de suppression d'un élément, mais ne permettent pas l'accès direct à un élément.

Les arbres binaires présentés ici sont en fait un compromis entre ces deux structures. Ils permettent un accès "relativement" rapide à un élément à partir de son identifiant, appelé ici une "clé". Dans les arbres binaires, l'ajout et la suppression sont également des opérations "relativement" rapides.

Par "relativement" rapide, on entend que le temps d'exécution d'une opération n'est pas proportionnel au nombre d'éléments dans la structure. En effet, dans un tableau non ordonné de 256 éléments par exemple, il faut parcourir au plus les 256 éléments pour trouver celui que l'on cherche. Comme vous le constaterez par la suite, dans un arbre binaire de 256 éléments, il suffit de parcourir au plus 8 éléments pour trouver celui que l'on cherche.

De la même manière qu'une liste chaînée, un arbre est constitué de maillons, appelés ici "noeuds", la différence étant qu'un noeud n'a pas un successeur mais deux. Ceux-ci sont désignés comme étant le "fils gauche" et le "fils droit" du noeud. Un noeud est donc une structure qui contient un élément à stocker et deux pointeurs sur les noeuds fils.

structure NOEUD:
ELEMENT elt;
NOEUD * fg;
NOEUD * fd;
fin structure;

Dans la suite de ce chapitre, on supposera que l'identifiant d'un élément, que l'on a appelé la clé, est un objet de type CLE. On disposera aussi de la fonction cle, cle(e) retournant la clé de l'élément e. On supposera également qu'un arbre ne peut pas contenir deux éléments ayant la même clé. La clé est donc un moyen unique d'identifier et de localiser un élément dans un arbre. La figure qui suit est l'exemple d'un arbre qui contient les éléments suivants:

(1;"Paris"), (4;"Bordeaux"), (7,"Marseille"), (12,"Lyon"), (16,"Toulouse").

Ici, la clé des éléments c'est le chiffre avant la chaîne de caractères. Ainsi, cle ((1;"Paris")) = 1. On peut remarquer que les éléments ne sont pas placés n'importe comment dans l'arbre. En effet, un arbre sera toujours fait de telle sorte que les éléments dans le sous-arbre gauche d'un noeud ont une clé inférieure à celle du noeud. De même, les éléments dans le sous-arbre droit d'un noeud ont une clé supérieure à celle du noeud. Ce qui facilite par la suite la recherche d'un élément par rapport à sa clé.

Le noeud au sommet de l'arbre est appelé "racine" et un arbre sera référencé simplement par un pointeur sur cette racine, de la même manière qu'une liste chaînée est référencée par un pointeur sur la tête de la liste.

type ARBRE: NOEUD *;

OPERATIONS SUR LA STRUCTURE

Introduction

Nous allons présenter ici quelques opérations classiques que l'on peut effectuer sur un arbre. On a choisi de les écrire de manière récursive car c'est la manière la plus simple d'aborder une telle structure de données. Voici maintenant une brève description des opérations détaillées dans cette section.

initialiserArbre(ARBRE * a)

Initialise l'arbre pointé par a, i.e. fait en sorte que l'arbre soit vide.

NOEUD * <-- preparerNoeud(ELEMENT e)

Alloue un noeud et y place l'élément e. Si aucun noeud n'a pu être alloué, la valeur NIL est retournée.

BOOLEEN <-- ajouterNoeud(ARBRE * a, NOEUD * n)

Insère le noeud pointé par n dans l'arbre pointé par a. Si un noeud avec la même clé existe déjà, l'insertion est annulée et la fonction retourne FAUX.

BOOLEEN <-- ajouterElement(ARBRE * a, ELEMENT e)

Insère un élément e dans l'arbre pointé par a. La fonction renvoie VRAI si l'opération a réussi.

BOOLEEN <-- existeCle(ARBRE a, CLE c)

Indique si un élément avec la clé c est présent dans l'arbre a.

NOEUD * <-- extraireMaximum(ARBRE * a)

Extrait le noeud de l'arbre pointé par a ayant la plus grande clé, i.e. enlève ce noeud de l'arbre et retourne son adresse. NIL est retournée s'il n'y a aucun noeud à extraire.

BOOLEEN <-- supprimerRacine(ARBRE * a)

Supprime le noeud à la racine de l'arbre pointé par a. FAUX est retournée s'il n'y a aucun noeud à supprimer.

BOOLEEN <-- extraireElement(ARBRE * a, CLE c, ELEMENT * e)

Extrait l'élément ayant la clé c de l'arbre pointé par a, i.e. le noeud contenant l'élément est supprimé de l'arbre et l'élément est copié à l'adresse pointée par e. VRAI est retournée si l'élément de clé c a été trouvé.

Préparation

Initialiser un arbre 

Cette fonction initialise les valeurs de la structure représentant l'arbre pointé par a, afin que celui-ci soit vide. Il suffit de mettre le pointeur sur la racine égal à NIL.

fonction initialiser(ARBRE * a):
*a <-- NIL;
fin fonction;

Préparer un noeud

Cette fonction alloue un nouveau noeud et place l'élément e à l'intérieur. Ses deux fils sont initialisés à la valeur NIL. La fonction retourne l'adresse de ce nouveau noeud. Au cas où l'allocation de mémoire échoue, NIL est renvoyée.

fonction NOEUD * <-- preparerNoeud(ELEMENT e):
n <-- ALLOUER(NOEUD,1);

si (n != NIL) alors
n --> elt <-- e;
n --> fg <-- NIL;
n --> fd <-- NIL;
fin si;

rendre n;
fin fonction;

Ajout

Ajouter un noeud

Cette fonction ajoute le noeud pointé par n dans l'arbre pointé par a. Pour cela, l'arbre est parcouru à partir de la racine pour descendre jusqu'à l'endroit où sera inséré le noeud. A chaque noeud, deux possibilités sont offertes pour descendre. On prendra à gauche si la clé du noeud visité est supérieure à la clé du noeud à insérer. A l'opposé, on prendra à droite si la clé du noeud visité est inférieure. En cas d'égalité, l'insertion ne peut pas se faire et la fonction retourne FAUX. On arrête la descente quand le fils gauche ou droit choisi pour descendre vaut NIL. Le noeud pointé par n est alors inséré à ce niveau.

fonction BOOLEEN <-- ajouterNoeud(ARBRE * a, NOEUD * n):
si (*a = NIL) alors
*a <-- n;
rendre VRAI;
fin si;

si (cle(n --> elt) = cle((*a) --> elt)) alors rendre FAUX;

si (cle(n --> elt) < cle((*a) --> elt)) alors
rendre ajouterNoeud(&((*a) --> fg),n);
fin si;

rendre ajouterNoeud(&((*a) --> fd),n);
fin fonction;

Ajouter un élément

Cette fonction ajoute l'élément e dans l'arbre pointé par a. Pour cela, un noeud est préparé puis ajouté dans l'arbre. Si le noeud ne peut pas être alloué ou si la clé de l'élément est déjà présente dans l'arbre, alors la valeur FAUX est retournée.

fonction BOOLEEN <-- ajouterElement(ARBRE * a, ELEMENT e):
n <-- preparerNoeud(e);
si (n = NIL) alors rendre FAUX;

si (non ajouterNoeud(a,n)) alors
LIBERER(n);
rendre FAUX;
fin si;

rendre VRAI;
fin fonction;

Parcours / Recherche

Clé existe ? 

Cette fonction cherche si un élément possède la clé c dans l'arbre a. Pour cela, l'arbre est parcouru à partir de la racine. Comme pour l'ajout d'un noeud, deux possibilités sont offertes quand on visite un noeud. Si on trouve l'élément qui a la clé c, alors VRAI est retournée. Sinon, on aboutit sur un fils (gauche ou droit) qui vaut NIL, ce qui signifie que la recherche est terminée et qu'aucun élément n'a la clé recherchée. FAUX est alors retournée.

fonction BOOLEEN <-- existeCle(ARBRE a, CLE c):
si (a = NIL) alors rendre FAUX;
si (c = cle(a --> elt)) alors rendre VRAI;
si (c < cle(a --> elt)) alors rendre existeCle(a --> fg,c);
rendre existeCle(a --> fd,c);
fin fonction;

Suppression

Extraire la clé maximum 

Cette fonction extrait le noeud qui a la plus grande clé dans l'arbre pointé par a. Pour cela, l'arbre est parcouru en descendant sur la droite tant que cela est possible. Le dernier noeud visité est celui recherché. Il est supprimé de l'arbre et son adresse est retournée. Au cas où l'arbre est vide, la valeur NIL est retournée.

fonction NOEUD * <-- extraireMaximum(ARBRE * a):
si (*a = NIL) alors rendre NIL;

si ((*a) --> fd = NIL) alors
n <-- *a;
*a <-- (*a) fg;
rendre n;
fin si;

rendre extraireMaximum(&((*a) --> fd));
fin fonction;

Supprimer la racine

Cette fonction supprime le noeud à la racine de l'arbre pointé par a. Quatre cas se présentent. Si l'arbre est vide, FAUX est retournée. Si la racine n'a pas de fils gauche, alors la racine est supprimée et le fils droit prend sa place. Si la racine n'a pas de fils droit, alors la racine est supprimée et le fils gauche prend sa place. Enfin, si la racine a deux fils, alors la racine est supprimée et le noeud ayant la plus grande clé dans le fils gauche prend sa place. Dans les trois derniers cas, VRAI est retournée.

fonction BOOLEEN <-- supprimerRacine(ARBRE * a):
si (*a = NIL) alors rendre FAUX;
n <-- *a;

si (n --> fg = NIL) alors *a <-- n --> fd;
sinon si (n --> fd = NIL) alors *a <-- n --> fg;
sinon
*a <-- extraireMaximum(&(n -->fg));
(*a) --> fg <-- n --> fg;
(*a) --> fd <-- n --> fd;
fin si;

LIBERER(n);
rendre VRAI;
fin fonction;

Extraire un élément 

Cette fonction extrait l'élément ayant la clé c de l'arbre pointé par a. L'élément extrait est stocké à l'adresse e. A partir de la racine, on parcours l'arbre jusqu'à trouver la clé c. A ce moment, l'élément du noeud trouvé est stocké à l'adresse e et le noeud est supprimé en appliquant la fonction supprimerRacine sur le sous-arbre dont la racine est le noeud en question.

fonction BOOLEEN <-- extraireElement(ARBRE * a, CLE c, ELEMENT * e):

si (*a = NIL) alors rendre FAUX;

si (c < cle((*a) --> elt)) alors
rendre extraireElement(&((*a) --> fg),c,e);
fin si;

si (c > cle((*a) --> elt)) alors
rendre extraireElement(&((*a) --> fd),c,e);
fin si;

*e <-- (*a) --> elt;
rendre supprimerRacine(a);
fin fonction;

EQUILIBRAGE DES ARBRES

Introduction

Très facilement, on peut se rendre compte que les arbres binaires tels qu'ils ont été présentés jusqu'à présent ont un inconvénient majeur. En effet, les opérations d'ajout et de suppression ne garantissent pas un certain équilibre de l'arbre, c'est-à-dire qu'il se peut qu'il y ait beaucoup plus de noeuds d'un côté que de l'autre. Cela signifie que la recherche d'une clé d'un côté sera plus lente qu'une recherche de l'autre côté. Pour illustrer cela, penchons-nous sur la figure suivante. Elle représente deux arbres. Celui de gauche résulte de l'ajout successif des clés a,b,c,d,e,f,g dans cet ordre, alors que celui de droite résulte de l'ajout des mêmes éléments dans l'ordre d,b,f,a,c,e,g.

On considérera par la suite qu'un arbre est équilibré si, pour chacun de ses noeuds, la différence entre la hauteur du sous-arbre gauche et la hauteur du sous-arbre droit est d'au plus une unité. Dans un premier temps, nous allons modifier la structure d'un noeud afin d'y intégrer des informations concernant l'équilibrage de l'arbre. Ensuite, nous présenterons des opérations appelées "rotations" qui permettent de rééquilibrer un arbre le cas échéant. Enfin, nous verrons à quelle occasion employer ces rotations et comment modifier les opérations présentées en première partie pour qu'elles guarantissent l'équilibre d'un arbre à tout moment.

Modification sur la structure

Introduction 

La structure de données présentée au début du chapitre est légèrement modifiée ici pour intégrer quelques informations concernant l'équilibrage de l'arbre. En fait, pour chaque noeud n, on rajoute un champ h qui indique la hauteur du sous-arbre de racine n, un arbre sans noeud ayant une hauteur égale à 0. Voici la nouvelle structure.

structure NOEUD:
ELEMENT elt;
NOEUD * fg;
NOEUD * fd;
ENTIER h;
fin structure;

Concernant cette nouvelle information, nous présentons maintenant les deux fonctions suivantes.

majHauteur(NOEUD * n)

Met à jour le champ h du noeud pointé par n en se basant sur les hauteurs (supposées correctes) des deux fils.

ENTIER <-- desequilibre(ARBRE a)

Mesure le déséquilibre de l'arbre a, i.e. retourne la différence entre la hauteur du sous-arbre gauche et celle du sous-arbre droit.

Mise à jour de la hauteur d'un noeud

Cette fonction met à jour le champ h du noeud pointé par n. L'actualisation est faite en se basant sur les champs h des fils du noeud. Si un fils vaut NIL, alors on considérera sa hauteur comme étant nulle. La hauteur du noeud pointé par n est donc la plus grande des deux hauteurs des fils augmentée d'une unité. On utilise l'instruction MAX qui retourne la plus grande des deux valeurs passées en paramètre.

fonction majHauteur(NOEUD * n):
si (n --> fg = NIL) alors hg <-- 0;
sinon hg <-- n --> fg --> h;

si (n --> fd = NIL) alors hd <-- 0;
sinon hd <-- n --> fd --> h;

n --> h <-- MAX(hd,hg) + 1;
fin fonction;

Mesure du déséquilibre d'un arbre 

Cette fonction retourne une valeur qui mesure le déséquilibre de l'arbre a. En fait, il s'agit de la différence entre la hauteur du sous-arbre gauche et celle du sous-arbre droit. Si un fils vaut NIL, alors on considérera sa hauteur comme étant nulle.

fonction ENTIER <-- desequilibre(ARBRE a):
si (a = NIL) alors rendre 0;

si (a --> fg = NIL) alors hg <-- 0;
sinon hg <-- a --> fg --> h;

si (a --> fd = NIL) alors hd <-- 0;
sinon hd <-- a --> fd --> h;

rendre (hg - hd);
fin fonction;

Les rotations

Pour rééquilibrer un arbre, nous allons utiliser deux types de rotation. La première est la rotation simple dont on présente deux alternatives symétriques: la rotation simple à droite (notée RD) et la rotation simple à gauche (notée RG). La seconde est la rotation double qui est une succession de deux rotations simples. On en présente également deux alternatives symétriques: la rotation double gauche-droite (notée RGD) et la rotation double droite-gauche (RDG).

Rotation RD

La figure suivante illustre l'opération de rotation simple à droite.

En supposant que tous les noeuds impliqués dans la rotation existent, voici la fonction qui effectue cette rotation sans oublier de mettre à jour la hauteur des noeuds déplacés.

fonction rotationRD(ARBRE * a):
n <-- *a;
si (n --> fg = NIL) alors /* Erreur */
*a <-- n --> fg;
n --> fg <-- (*a) -->fd;
(*a) --> fd <-- n;
majHauteur(n);
majHauteur(*a);
fin fonction;

Rotation RG

La rotation simple à gauche est symétrique à la rotation simple à droite. Les notions de gauche et de droite sont simplement inversées.

fonction rotationRG(ARBRE * a):
n <-- *a;
si (n --> fd = NIL) alors /* Erreur */

*a <-- n --> fd;
n --> fd <-- (*a) --> fg;
(*a) --> fg <-- n;
majHauteur(n);
majHauteur(*a);
fin fonction;

Rotation RGD

La figure suivante illustre l'opération de rotation double gauche-droite. Il s'agit d'appliquer une rotation RG sur le fils gauche de la racine, puis d'appliquer une rotation RD sur la racine elle-même.

En supposant que tous les noeuds impliqués dans la rotation existent, voici la fonction qui effectue cette rotation.

fonction rotationRGD(ARBRE * a):
si ((*a) --> fg = NIL) alors /* Erreur */
rotationRG(&((*a) --> fg));
rotationRD(a);
fin fonction;

Rotation RDG

La rotation double droite-gauche est symétrique à la rotation double gauche-droite. Les notions de gauche et de droite sont simplement inversées.

fonction rotationRDG(ARBRE * a):
si ((*a) --> fd = NIL) alors /* Erreur */
rotationRD(&((*a) --> fd));
rotationRG(a);
fin fonction;

Opérations d'ajout et de suppression avec rééquilibrage

Les opérations d'ajout et de suppression d'un élément présentées ici guarantissent qu'un arbre reste toujours équilibré. L'idée principale est la suivante. On effectue tout d'abord l'opération d'ajout ou de suppression comme elle a été présentée précédemment. Seulement, on mémorise le chemin qui nous a permis de trouver la position de l'élément inséré ou supprimé.
Ensuite, on remonte ce chemin jusqu'à la racine. A chaque noeud visité, on regarde s'il y a un déséquilibre de plus d'une unité. Si c'est le cas, un rééquilibrage s'impose en effectuant une des quatre rotations présentées précédemment.

Dans un premier temps, on présente la fonction de rééquilibrage qui effectue l'une des quatres rotations sur la racine d'un arbre dans le but de le rééquilibrer. Ensuite, on détaille les modifications apportées aux opérations suivantes pour que l'ajout et la suppression guarantissent l'équilibre de l'arbre à tout moment.
ajouterNoeud, extraireMaximum, extraireElement.

Rééquilibrer un arbre

Cette fonction rééquilibre l'arbre pointé par a en effectuant l'une des quatres rotations présentées. Cette opération suppose que les sous-arbres de la racine sont équilibrés. Elle est exécutée après l'ajout ou la suppression d'un élément sur un arbre équilibré. Un rééquilibrage sera effectué si le déséquilibre vaut +2 ou -2. On détaille ici le cas où le déséquilibre vaut +2, le cas -2 étant symétrique. Dans ce cas, il y a un déséquilibre à gauche. Trois possibilités se présentent alors: le déséquilibre du fils gauche vaut +1, 0 ou -1. Dans le premier cas, une rotation simple à droite rééquilibre l'arbre.

Le deuxième cas ne peut pas se produire, car cela signifierait que l'arbre était déjà déséquilibré avant la suppression ou l'ajout d'un élément.

Dans le dernier cas, une rotation double gauche-droite rééquilibre l'arbre.

Voici donc le code de la fonction de rééquilibrage.

fonction reequilibrer(ARBRE * a):
d <-- desequilibre(*a);

si (d = +2) alors
si (desequilibre((*a) --> fg) = -1) alors
   rotationRGD(a);
sinon
   rotationRD(a);
fin si;
sinon si (d = -2) alors
si (desequilibre((*a) --> fd) = +1) alors
   rotationRDG(a);
sinon
   rotationRG(a);
fin si;
fin si;
fin fonction;

Ajouter un noeud (avec rééquilibrage)

Les modifications apportées à cette fonction sont les suivantes. Tout d'abord, le noeud inséré se voit attribué une hauteur de 1. Ensuite, après chaque appel récursif à la fonction, la hauteur du noeud racine est mise à jour et une action de rééquilibrage est engagée sur ce même noeud. En effet, après chaque appel récursif, l'arbre est susceptible d'être déséquilibré puisqu'un élément y a été ajouté.

fonction BOOLEEN <-- ajouterNoeud(ARBRE * a, NOEUD * n):
si (*a = NIL) alors
*a <-- n;
n --> h <-- 1;
rendre VRAI;

si (cle(n --> elt) = cle((*a) --> elt)) alors rendre FAUX;

si (cle(n --> elt) < cle((*a) --> elt)) alors
ok <-- ajouterNoeud(&((*a) --> fg),n);
sinon
ok <-- ajouterNoeud(&((*a) --> fd),n);
fin si;

si (ok) alors
majHauteur(*a);
reequilibrer(a);
fin si;

rendre ok;
fin fonction;

Extraire la clé maximum (avec rééquilibrage)

Les modifications apportées à cette fonction sont les suivantes. Après chaque appel récursif à la fonction, la hauteur du noeud racine est mise à jour et une action de rééquilibrage est engagée sur ce même noeud. En effet, après chaque appel récursif, l'arbre est susceptible d'être déséquilibré puisqu'un élément y a été supprimé.

fonction NOEUD * <-- extraireMaximum(ARBRE * a):
si (*a = NIL) alors rendre NIL;

si ((*a) --> fd = NIL) alors
n <-- *a;
*a <-- (*a) --> fg;
rendre n;
fin si;

n <-- extraireMaximum(&((*a) --> fd));

si (n != NIL) alors
majHauteur(*a);
reequilibrer(a);
fin si;

rendre n;
fin fonction;

Extraire un élément (avec rééquilibrage) 

fonction BOOLEEN <-- extraireElement(ARBRE * a, CLE c, ELEMENT * e):

si (*a = NIL) alors rendre FAUX;

si (c < cle((*a) --> elt)) alors
ok <-- extraireElement(&((*a) --> fg),c,e);
sinon si (c > cle((*a) --> elt)) alors
ok <-- extraireElement(&((*a) --> fd),c,e);

sinon
*e <-- (*a) elt;
ok <-- supprimerRacine(a);
fin si;

si (ok et *a != NIL) alors
majHauteur(*a);
reequilibrer(a);
fin si;

rendre ok;
fin fonction;

CONCLUSION

Cette structure de données est un compromis entre le tableau et la liste chaînée puisqu'elle permet l'accès, l'insertion et la suppression d'un élément "relativement" rapidement. Cependant, pour que cela soit possible, il faut s'assurer de l'équilibre de l'arbre, chose assez compliquée à mettre en place. Les opérations ont été présentées ici de manière récursive, car leur compréhension en est plus simple. Mais le lecteur est invité à réécrire ces opérations de manière itérative. Elles seront plus compliquées mais nettement plus efficaces.

------------------------------------------------------------------------------------------------------
<<< CHAPITRE IV: FILES D'ATTENTE