Apprendre à programmer les arbres en langage C - Deuxième partie

Après les arbres binaires de recherche, nous allons voir un nouveau type d'arbres : les arbres tassés, appelés aussi tas (heap en anglais). Ce sont aussi des arbres binaires.

Sur les arbres binaires de recherche, 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 est complet). Bien sûr comme dans tout arbre, les données seront insérées selon un certain ordre, afin de les retrouver facilement. Ce type d'arbre est très bien adapté pour servir de file de priorité. C'est ce que nous allons construire dans l'exemple suivant.

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, où 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. (À 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'entiers pour notre exemple, mais aussi deux informations, la taille du tableau, c'est-à-dire le nombre d'éléments valides 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éments. 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ée 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é à la racine de l'arbre (case d'indice 1 du tableau). Les éléments seront donc positionnés de telle sorte que la valeur de leurs parents leur soit supérieure et celle de leurs enfants leur soit inférieure ou égale. Mais alors, comment insérer les éléments, et bien ils seront insérés à la première position vide du tableau (celle qui correspond au nœud marqué suivant sur le schéma de l'arbre ci-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 insère 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 insérer 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é maximale 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. 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, puisqu'il est à la racine de l'arbre. Où ça se complique c'est pour réorganiser les éléments restants. La méthode 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'ait 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 n'en 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.

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 __cplusplus
extern "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 parcourra 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.

Bonne lecture,

CGi.

Nous tenons à remercier Claude Leloup pour la relecture orthographique et Malick SECK pour la mise au gabarit.