Embed Size (px)
DESCRIPTION
Les arbres TAS en C
Citation preview
Les arbres en C.
1 - Implémentation d'un arbre simple.
Introduction :
Je ne vais pas vous faire un cours complet sur les arbres, mais vous montrer comment les implémenter en langage C.Voyons tout de même quelques notions élémentaires pour qu'il n'y ait pas ambiguïtés :Qu'est-ce qu'un arbre ?Tout comme les listes chaînées, les arbres servent à mémoriser des données. Ils sont constitués d'éléments que l'on appelle souvent des nœuds (node). Ils sont semblables aux listes chaînées par le fait que les éléments sont chaînés les uns avec les autres, mais avec la possibilité que plusieurs branches partent d'un nœud, d'ou leur nom. (On pourrait très bien voir une liste chainée comme un arbre à une seule branche). Il est courant d'appeler le premier élément d'un arbre la racine. La racine est un nœud qui n'a pas de parent. On peut aussi entendre parler de feuilles, ce sont les nœuds qui sont au bout des branches et qui n'ont donc pas d'enfants.Cet article étant destiné à aborder les arbres, nous allons donc en créer un qui sera le plus simple possible, ce sera un arbre binaire.Un arbre binaire est un arbre ou chaque nœud peut avoir au maximum deux branches. Pour différencier les branches, on les nomme souvent droite ou gauche (right, left).On peut se faire un petit schéma pour se le représenter visuellement.
La racine en haut et les branches vers le bas, désolé mais c'est la représentation la plus courante pour les arbres (informatique).Pour qu'un arbre soit efficace, il ne faut pas le remplir anarchiquement mais de façon ordonnée, ceci afin de retrouver nos données rapidement et sans avoir à parcourir l'arbre complet. C'est là son gros avantage par rapport aux listes chaînées. Il est souvent bien plus rapide de parcourir l'arbre de la racine jusqu'à une feuille qu'une longue liste chaînée parfois entièrement.
Un arbre binaire de recherche :
C'est un des arbres les plus simples, et nous allons le simplifier au maximum. Ses éléments (ou nœuds) ne contiendront qu'une valeur de type entier. (On aurait pu y embarquer des structures de données plus complexe, mais ça ne nous est pas utile et ça surchargerait l'exemple). C'est cette valeur qui nous servira à
ordonner les éléments. Nous l'appellerons donc la clé (key).Tout comme les listes chaînées, les arbres sont basés sur une structure du langage C. La différence sera quelle contiendra deux pointeurs pour lier les éléments, un pointeur pour accéder à la branche de gauche et l'autre pour accéder à la branche de droite. Nous avons maintenant suffisamment d'éléments pour constituer la structure d'un nœud.
typedef struct node{ unsigned int key; struct node *left; struct node *right;} node ;
La deuxième étape est de trier les éléments à leur insertion dans l'arbre. Le tri sera effectué sur la valeur de la clé (key). Le premier élément est inséré à la racine de l'arbre, l'élément suivant est inséré à gauche si la valeur de sa clé est inferieure à celle de la racine et à droite si la valeur de sa clé est supérieure à celle de la racine. (On aurait pu faire l'inverse). Pour les éléments qui suivent, c'est le même principe jusqu'à trouver un emplacement libre au bout d'une branche.Par exemple si on avait inséré des éléments ayant comme clé ; 10, 20, 4, 8, 5, 15, 3 dans cet ordre, on aurait un arbre équivalent au schéma suivant :
Comme vous le voyez, il va être facile de retrouver un élément, il suffira de suivre le même cheminement que pour l'insertion.Pour notre exemple, le point d'entrée de l'arbre sera un pointeur initialisé à NULL qui devra pointer sur la racine dès l'insertion du premier élément.
node *Arbre = NULL;
La première chose que l'on peut faire, c'est donc d'insérer des éléments. Pour cela, nous allons créer la fonction addNode.
void addNode(node **tree, unsigned int key){ node *tmpNode; node *tmpTree = *tree;
node *elem = malloc(sizeof(node)); elem->key = key; elem->left = NULL; elem->right = NULL;
if(tmpTree) do { tmpNode = tmpTree; if(key > tmpTree->key ) { tmpTree = tmpTree->right; if(!tmpTree) tmpNode->right = elem; } else { tmpTree = tmpTree->left; if(!tmpTree) tmpNode->left = elem; } } while(tmpTree); else *tree = elem;}
Sa fonction est de créer l'élément à l'aide de la fonction malloc, d'initialiser ses champs : la clé avec la valeur désiré (passé en paramètre à la fonction), d'initialiser les deux pointeurs à NULL (il sera positionné au bout d'une branche et n'a donc pas d'enfants) et de l'insérer dans l'arbre en tenant compte des critères de tri. Donc si l'élément n'est pas le premier, on boucle (boucle do while) afin d'avancer de nœud en nœud jusqu'a atteindre un emplacement libre (pointeur à NULL) et à chaque nœud on part à droite si la clé est supérieure à celle du nœud courant ou à gauche si elle est inférieure ou égale à celle du nœud courant.Le cas du premier élément (racine de l'arbre) impose d'affecter l'adresse de cet élément au pointeur sur l'arbre que l'on a passé en paramètre à la fonction. Il s'impose donc que ce paramètre soit un pointeur de pointeur afin de passer l'adresse du pointeur sur l'arbre à la fonction. Fonction que l'on appellera donc de la façon suivante :
node *Arbre = NULL;//...
addNode(&Arbre, 30);
Comme on peut le remarquer, ce n'est guère plus compliqué que pour une liste chaînée.Remarque: Je n'ai pas testé les retours de la fonction malloc pour ne pas surcharger le code.
Nous avons dit que notre arbre est un arbre de recherche. C'est donc la deuxième fonction que nous allons créer. Elle devra nous indiquer si un élément avec une clé de valeur x est présent dans l'arbre.
int searchNode(node *tree, unsigned int key){ while(tree) { if(key == tree->key) return 1;
if(key > tree->key ) tree = tree->right; else tree = tree->left; } return 0;}
Le principe est identique à la fonction d'insertion. On suit le cheminement en partant à droite ou à gauche selon la valeur de la clé. A chaque nœud on vérifie si on est en présence de l'élément recherché, si oui on retourne la valeur 1. Quand on arrive au bout de la branche si on ne l'a pas trouvé on retourne 0. On est certain qu'il ne se trouve pas dans une autre branche. Il n'y a donc pas besoin de tester.Si la structure était plus complexe, nous aurions pu faire retourner un contenu par la fonction. Par exemple une valeur si on avait eu un couple clé valeur.L'appel de cette fonction est des plus simples :
if(searchNode(Arbre, Key)) //...
A ce stade nous avons déjà un arbre opérationnel.Mais nous n'allons pas nous arrêter là, nous allons lui ajouter une fonction qui permettra d'afficher l'arbre et trié en plus.Pour cela il va falloir parcourir l'arbre complet, et là nous avons guère le choix si l'on veut faire cela de façon simple, nous devons utiliser des fonctions récursives. (Une fonction récursive est une fonction qui s'appelle-elle même).
void printTree(node *tree){ if(!tree) return;
if(tree->left) printTree(tree->left);
printf("Cle = %d\n", tree->key);
if(tree->right) printTree(tree->right);}
Dans la fonction, on remarque deux appels récursifs de la fonction, un sur le pointeur de gauche et l'autre sur le pointeur de droite de l'élément en cours de traitement. Ce qui va permettre de passer d'élément en élément.Ce qui ferra arrêter la récursivité dans notre fonction, c'est le test du pointeur NULL des feuilles.Pour afficher les valeurs des clés dans l'ordre, il faut partir à gauche toute avant d'afficher la clé au retour de la fonction, par contre si l'on part à droite, on affiche la clé en cours avant l'appel de la fonction. (Vous pouvez essayer de suivre le cheminement sur le schéma).
Allez ! Une autre fonction d'affichage très semblable à la précédente, sauf que l'on part à droite toute en premier.
void printReverseTree(node *tree){ if(!tree) return;
if(tree->right) printReverseTree(tree->right);
printf("Cle = %d\n", tree->key);
if(tree->left) printReverseTree(tree->left);}
Vous avez testé ! Ça affiche l'arbre trié en sens inverse tout simplement.Une dernière fonction nécessaire dans notre exemple, nous avons alloué de la mémoire avec malloc, il faut donc la libérer. Là aussi il faut parcourir l'arbre complet, nous utiliserons donc le même principe que pour les fonctions d'affichage.
void clearTree(node **tree){ node *tmpTree = *tree;
if(!tree) return;
if(tmpTree->left) clearTree(&tmpTree->left);
if(tmpTree->right) clearTree(&tmpTree->right);
free(tmpTree);
*tree = NULL;}
L'utilisation est des plus simples. Je mets un code d'utilisation en bas de page (main.c) qui vaut mieux qu'un grand discours.
Codes sources de l'exemple :
Pour plus de lisibilité et de possibilité de réutilisation de cet arbre, nous séparerons son code de son utilisation.
rbtree.h :
#ifndef CGI_RBTREE_H#define CGI_RBTREE_H
typedef struct node{ unsigned int key; struct node *left; struct node *right;} node ;
#ifdef __cplusplusextern "C" {#endif
void addNode(node **tree, unsigned int key);
int searchNode(node *tree, unsigned int key);
void printTree(node *tree);
void printReverseTree(node *tree);
void clearTree(node **tree);
#ifdef __cplusplus}#endif
#endif //CGI_RBTREE_H
rbtree.c :
#include <stdio.h>#include <stdlib.h>#include "rbtree.h"
void addNode(node **tree, unsigned int key){ node *tmpNode; node *tmpTree = *tree;
node *elem = malloc(sizeof(node)); elem->key = key; elem->left = NULL; elem->right = NULL;
if(tmpTree) do { tmpNode = tmpTree; if(key > tmpTree->key ) {
tmpTree = tmpTree->right; if(!tmpTree) tmpNode->right = elem; } else { tmpTree = tmpTree->left; if(!tmpTree) tmpNode->left = elem; } } while(tmpTree); else *tree = elem;}
/***************************************************************************/
int searchNode(node *tree, unsigned int key){ while(tree) { if(key == tree->key) return 1;
if(key > tree->key ) tree = tree->right; else tree = tree->left; } return 0;}
/***************************************************************************/
void printTree(node *tree){ if(!tree) return;
if(tree->left) printTree(tree->left);
printf("Cle = %d\n", tree->key);
if(tree->right) printTree(tree->right);}
/***************************************************************************/
void printReverseTree(node *tree){ if(!tree) return;
if(tree->right) printReverseTree(tree->right);
printf("Cle = %d\n", tree->key);
if(tree->left) printReverseTree(tree->left);}
/***************************************************************************/
void clearTree(node **tree){ node *tmpTree = *tree;
if(!tree) return;
if(tmpTree->left) clearTree(&tmpTree->left);
if(tmpTree->right) clearTree(&tmpTree->right);
free(tmpTree);
*tree = NULL;}
Voici un exemple d'utilisation de l'arbre que nous venons de construire.
main.c :
#include <stdio.h>#include <stdlib.h>
#include "rbtree.h"
int main(){ unsigned int Key; node *Arbre = NULL;
addNode(&Arbre, 30); addNode(&Arbre, 20); addNode(&Arbre, 50); addNode(&Arbre, 45); addNode(&Arbre, 25); addNode(&Arbre, 80); addNode(&Arbre, 40); addNode(&Arbre, 70); addNode(&Arbre, 25); addNode(&Arbre, 10); addNode(&Arbre, 60);
puts("-------------------------------");
printTree(Arbre);
puts("-------------------------------");
printReverseTree(Arbre);
puts("-------------------------------");
Key = 30; if(searchNode(Arbre, Key)) printf("La cle %d existe.\n", Key); else printf("La cle %d n'existe pas.\n", Key);
Key = 32; if(searchNode(Arbre, Key)) printf("La cle %d existe.\n", Key); else printf("La cle %d n'existe pas.\n", Key);
puts("-------------------------------");
clearTree(&Arbre);
return 0;}
Cet arbre est bien adapté pour la recherche d'élément, l'insertion et la recherche ne nécessite pas de parcourir l'arbre en entier. Il peut aussi faire du tri, vous l'avez vu avec les fonctions d'affichage. Il est même assez performant si les valeurs des clés des éléments insérés sont aléatoires.Par contre il devient très mauvais dans le cas d'insertion d'éléments déjà triés ou partiellement triés. Dans ce
cas au lieu de faire plusieurs branches il pourrait en faire une seule, très grande dans le pire des cas. (Ce qui reviendrait à une liste chainée).
2 - Implémentation d'un tas (heap).
Introduction :
Après les arbres binaires de recherche, nous allons voir un nouveau type d'arbres : les arbres tassés, appelé aussi tas (heap en anglais). Ce sont aussi des arbres binaires.Sur les arbres binaires de recherches nous avions mentionné un défaut, qui est le fait que certaines branches peuvent être beaucoup plus longues que d'autres dans certaines circonstances. Ce qui a un effet néfaste sur les performances. L'arbre que nous allons aborder pallie à ce problème. La hauteur de sa plus grande branche ne pourra être supérieure que d'une unité par rapport à la plus petite. C'est à dire que si sa plus grande branche passe par 15 nœuds sa plus petite passera par 14 nœuds au minimum (15 au cas où l'arbre soit complet). Bien sûr comme tous arbres, les données seront insérées selon un certain ordre, afin de les retrouver facilement. Ce type d'arbre est très bien adapter pour servir de file de priorité. C'est ce que nous allons construire dans l'exemple suivant.
Le tas :
Comme les structures des articles précédents nous la ferons le plus simple possible, la valeur sauvegardée sera donc encore une fois un entier.Mais cette fois nous allons faire une implémentation complètement différente de ce que l'on a vu jusqu'à maintenant. Nous n'allons plus utiliser d'éléments chaînés par des pointeurs, mais un tableau dynamique. Cette façon de procéder peut paraître étrange au premier abord, mais est très bien adaptée à ce type d'arbre. Pour comprendre le principe nous allons suivre le schéma suivant, ou les éléments de l'arbre représentent les indices du tableau et non pas leur valeur.
Première remarque, l'indice du premier élément est 1, il est positionné à la racine de l'arbre (ou au sommet du tas). La case d'indice 0 du tableau ne sera pas utilisée. Cela nous permettra de mieux visualiser le fonctionnement de cet arbre. (A savoir que l'on aurait pu tout à fait commencer avec l'indice 0, ce n'est qu'un choix). Nous remarquons donc sur le schéma qu'il est assez simple de calculer l'indice des enfants d'un nœud, puisque l'indice du fils gauche est l'indice du parent multiplié par 2 et l'indice du fils droit est l'indice
du fils gauche plus 1. Nous pouvons donc parcourir une branche sans parcourir tout le tableau. Vous devez commencer à percevoir les avantages d'un tel système.Le point d'entrée de notre tas sera une structure qui contiendra un pointeur sur le tableau de données, tableau d'entier pour notre exemple, mais aussi deux informations, la taille du tableau, c'est à dire le nombre d'élément valide qu'il contient et la capacité du tableau, c'est à dire sa taille réelle, comprenant les cases non utilisées. Ceci dans le but d'éviter des réallocations à chaque ajout d'élément. Le tableau sera agrandi seulement quand sa taille aura atteint la capacité du tableau.
typedef struct{ int capacity; int size; int *tab;} Heap;
Première chose à faire, créer et initialiser la structure. Pour cela nous allons créer une fonction nommée : CreateHeap, elle nous retournera un pointeur initialisé sur une structure Heap.
Heap* createHeap(void){ Heap *heap = malloc(sizeof(Heap)); if(!heap) return NULL; heap->tab = malloc(32*sizeof(int)); /* Prévoir l'échec de malloc */ heap->capacity = 32; heap->size = 0; return heap;}
On crée une variable du type Heap avec malloc, puis on créé le tableau nommé tab de taille 32. (Je n'ai pas testé le retour de malloc pour ne pas surcharger l'exemple). Nous mettons donc le champ capacity à 32 et size à 0 (le tableau est vide).
Nous avons dit précédemment que notre arbre se comportera comme une file de priorité. Nous ferons donc en sorte que le premier élément qui sera extrait du tas sera celui qui à la plus grande valeur (on aurait pu faire l'inverse). Pour le trouver facilement, il sera donc positionnés à la racine de l'arbre (case d'indice 1 du tableau). Les éléments serons donc positionné de tel sorte que la valeur de leurs parents leurs soit supérieure et celle de leurs enfants leur soit inferieures ou égal. Mais alors comment insérer les éléments, et bien ils seront inséré à la première position vide du tableau (celle qui correspond au nœud marqué suivant sur le schéma de l'arbre si dessus). Ensuite il faut faire remonter l'élément par échange avec son parent, tant que sa valeur est supérieure à celle de son parent. Par exemple si on insert des éléments ayant comme valeur ; 12, 11, 14, 8, 13, 7, 18, 6, 1, 10, 3 dans cet ordre, on aurait un arbre équivalent au schéma suivant :
Après avoir créé le tas,
Heap *tas = CreateHeap();
Nous allons voir la fonction utilisée pour inserer les éléments :
void pushNode(Heap *heap, int value){ if(heap->size >= heap->capacity) HeapRealloc(heap); heap->size++; heap->tab[heap->size] = value; reorganizeHeap(heap);}
Si la capacité maximum du tableau est atteinte, on l'agrandira en appelant la fonction HeapRealloc (Code en bas de page). Comme on a ajouté un élément, il faut donc incrémenter la taille (champ size). Puis, on met l'élément dans la dernière case valide du tableau, c'est celle qui a l'indice heap->size. Ensuite comme mentionné précédemment il faut déplacer l'élément à la bonne place. Ce sera le rôle de la fonction reorganizeHeap :
static void reorganizeHeap(Heap *heap){ int tmp; int size = heap->size; int index = size/2; while(heap->tab[index] < heap->tab[size] && size>1) { tmp = heap->tab[size]; heap->tab[size] = heap->tab[index]; heap->tab[index] = tmp;
index/=2; size/=2; }}
Pour atteindre les fils d'un parent on avait dit qu'il fallait multiplier l'indice du parent par 2. Mais là nous nous trouvons dans la situation inverse, donc pour retrouver le parent d'un fils, il suffit de le diviser par 2 tout simplement. C'est ce que nous ferons dans la fonction reorganizeHeap pour remonter l'élément par échange avec son parent tant qu'il est supérieur à son parent.
Maintenant voyons la fonction inverse, c'est à dire le retrait d'un élément. Le retrait de l'élément est simple puis qu'il est à la racine de l'arbre. Ou ça ce complique c'est pour réorganiser les éléments restant. La methode est de mettre le dernier élément à la racine. On n'oublie pas de diminuer la taille de 1 (il y a un élément en moins). Mais cet élément n'est plus à sa place, il faut donc le descendre par échange avec le plus grand de ses fils tant qu'il est supérieur à l'élément ou qu'il n'ai plus de fils.
int popNode(Heap *heap){ int tmp; int indexUp = 1; int indexDn = 2;
if(heap->size==0) return -1;
int value = heap->tab[1]; heap->tab[1] = heap->tab[heap->size]; heap->size--;
while(indexDn<=heap->size) {
if(indexDn+1 <= heap->size && heap->tab[indexDn] < heap->tab[indexDn+1]) { indexDn++; } if(heap->tab[indexDn] > heap->tab[indexUp]) { tmp = heap->tab[indexDn]; heap->tab[indexDn] = heap->tab[indexUp]; heap->tab[indexUp] = tmp; } indexUp = indexDn; indexDn *= 2; } return value;}
Bien évidemment, une fonction pour libérer la mémoire allouée quand on en n'a plus besoin.
void freeHeap(Heap *heap){ free(heap->tab); free(heap);}
L'utilisation est des plus simples. Je mets un code d'utilisation en bas de page (main.c) qui vaut mieux qu'un grand discours.
Codes sources de l'exemple :
Pour plus de lisibilité et de possibilité de réutilisation de cet arbre, nous séparerons son code de son utilisation.
heap.h :
#ifndef CGI_HEAP_H#define CGI_HEAP_H
typedef struct{ int capacity; int size; int *tab;}Heap;
#ifdef __cplusplusextern "C" {#endif
Heap* createHeap(void);
void pushNode(Heap *heap, int value);
int popNode(Heap *heap);
void freeHeap(Heap *heap);
#ifdef __cplusplus}#endif
#endif //CGI_HEAP_H
heap.c :
#include <stdlib.h>#include "heap.h"
static void HeapRealloc(Heap *heap);static void reorganizeHeap(Heap *heap);
Heap* createHeap(void){ Heap *heap = malloc(sizeof(Heap)); if(!heap) return NULL; heap->tab = malloc(32*sizeof(int)); /* Prévoir l'échec de malloc */ heap->capacity = 32; heap->size = 0; return heap;}
/***************************************************************************/static void HeapRealloc(Heap *heap){ int new_size = 2*heap->capacity; heap->tab = realloc(heap->tab, new_size*sizeof(int)); /* Prévoir l'échec de realloc */ heap->capacity = new_size;}
/***************************************************************************/static void reorganizeHeap(Heap *heap){ int tmp; int size = heap->size; int index = size/2; while(heap->tab[index] < heap->tab[size] && size>1) { tmp = heap->tab[size]; heap->tab[size] = heap->tab[index]; heap->tab[index] = tmp;
index/=2; size/=2; }}
/***************************************************************************/void pushNode(Heap *heap, int value){ if(heap->size >= heap->capacity) HeapRealloc(heap); heap->size++; heap->tab[heap->size] = value; reorganizeHeap(heap);}
/***************************************************************************/int popNode(Heap *heap){ int tmp; int indexUp = 1; int indexDn = 2;
if(heap->size==0) return -1;
int value = heap->tab[1]; heap->tab[1] = heap->tab[heap->size]; heap->size--;
while(indexDn<=heap->size) { if(indexDn+1 <= heap->size && heap->tab[indexDn] < heap->tab[indexDn+1])
{ indexDn++; } if(heap->tab[indexDn] > heap->tab[indexUp]) { tmp = heap->tab[indexDn]; heap->tab[indexDn] = heap->tab[indexUp]; heap->tab[indexUp] = tmp; } indexUp = indexDn; indexDn *= 2; } return value;}
/***************************************************************************/void freeHeap(Heap *heap){ free(heap->tab); free(heap);}
Voici un exemple d'utilisation de l'arbre que nous venons de construire.
main.c :
#include <stdio.h>#include "heap.h"
int main(){ Heap *tas = createHeap();
pushNode(tas, 12); pushNode(tas, 11); pushNode(tas, 14); pushNode(tas, 8); pushNode(tas, 13); pushNode(tas, 7); pushNode(tas, 18); pushNode(tas, 6); pushNode(tas, 1); pushNode(tas, 10); pushNode(tas, 3);
printf("Valeur retiree : %d\n", popNode(tas)); printf("Valeur retiree : %d\n", popNode(tas)); printf("Valeur retiree : %d\n", popNode(tas)); printf("Valeur retiree : %d\n", popNode(tas)); printf("Valeur retiree : %d\n", popNode(tas)); printf("Valeur retiree : %d\n", popNode(tas)); printf("Valeur retiree : %d\n", popNode(tas)); printf("Valeur retiree : %d\n", popNode(tas)); printf("Valeur retiree : %d\n", popNode(tas)); printf("Valeur retiree : %d\n", popNode(tas)); printf("Valeur retiree : %d\n", popNode(tas)); freeHeap(tas);
return 0;}
Si l'on compare à une liste chaînée triée. Le retrait de l'élément de tête est comparable car dans les deux cas il n'y a pas besoin de parcourir la liste. Mais pour l'insertion d'un élément c'est tout autre chose. Pour la liste dans le pire des cas on parcourira la liste complète, alors que pour le tas ça sera la hauteur d'une branche au maximum. Ce qui pour des structures de données comportant un très grand nombre d'éléments n'est plus négligeable.
