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)
    
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 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

Article plus récent Article plus ancien

Leave a Reply