TP4 : BST et AVL¶

Binary Tree Search¶

Comme vu en cours, les arbres binaires de recherche (ABR en francais ou BST en anglais) sont des arbres binaires (2 fils au plus par noeud) qui vérifient une propriété d'ordre : le fils gauche est toujours plus petit que son père, et le fils droit plus grand.

Fonctions de bases¶

Dans un fichier bst.h vous allez définir des structures de donnée et des types permettant de manipuler des BST
- BSTNode sera le nom d'un type équivalent à une structure contenant (attention à respecter les noms)
  - un pointeur vers un Elmt_t appellé data (vous pouvez réutiliser la librairie Elmt.h du tp précédant pour laquelle un Elmt_t est simplement un int)
  - un pointeur vers un BSTNode appellé ls (left son)
  - un pointeur vers un BSTNode appellé rs (right son)
- BST sera un type équivalent à un pointeur sur un BSTNode
écrivez les fonctions basiques suivantes :
- BST create_empty_BST(); -- renvoie NULL
- int is_empty(BST); -- renvoie 1 si l'arbre est vide (racine == NULL), 0 sinon
- int is_leaf(BSTNode*) -- renvoie 1 si le noeud est une feuille (deux fils == NULL), 0 sinon
- BSTNode* create_node(Elmt_t *);
  - alloue dynamiquement un nouveau BSTNode
  - initialise ses trois champs (data avec le pointeur passé en paramètre et les deux autres à NULL)
  - renvoie le pointeur vers le nouveau noeud (ou NULL si problème d'allocation)
La fonction add Pour ajouter un élément à un arbre, il faut d'abord trouver où il va. On peut utiliser l'algorithme récursif suivant :

arbre AJOUTER(element x, arbre A)
    si A est vide
        arbre B = creer un noeud avec l'element x
        A = B;
        renvoyer A
    sinon si x < racine de A
            fils gauche de A = AJOUTER(x,fils gauche de A)
            retourner A
    sinon si x > racine de A
            fils droit de A = AJOUTER(x,fils droit de A)
            retourner A
    sinon retourner A (pas d'ajout)

Ou dit autrement, on cherche l'élément dans l'arbre, si on le trouve on ne fait rien, si on arrive à une feuille on insère l'élément comme fils de cette feuille. Écrivez en C la procédure void add(Elmt_t*,BST* t, int (*compare_elmt)(Elmt_t*, Elmt_t*)); Notez la difficulté ici : dans la procédure donnée, le passage de l'arbre se fait par copie, dans la fonction demandée, il se fait par adresse.

Parcourir l'arbre¶

Écrivez les trois fonctions d'affichage de l'arbre en profondeur possibles
- void print_prefix(BST t); procédure récursive qui affiche la racine puis le sous arbre gauche et enfin le sous arbre droit
- void print_infix(BST t); procédure récursive qui affiche le sous arbre gauche puis la racine et enfin le sous arbre droit
- void print_postfix(BST t); procédure récursive qui affiche le sous arbre gauche puis le sous arbre droit et enfin la racine
Testez votre code avec le main() suivant (à écrire dans un fichier test.c)

int main()
{
    int n1 = 1;
    int n2 = 2;
    int n3 = 3;
    int n4 = 4;
    int n5 = 5;

    BST t = create_empty_BST();

    add(&n1,&t,&compare_int);
    add(&n2,&t,&compare_int);
    add(&n3,&t,&compare_int);
    add(&n4,&t,&compare_int);
    add(&n5,&t,&compare_int);

    printf("Affichage prefixé : \n");   
    print_prefix(t);/* R G D */
    printf("\n");

    printf("Affichage infixé : \n");    
    print_infix(t); /* G R D */
    printf("\n");

    printf("Affichage postfixé : \n");  
    print_postfix(t); /* G D R */
    printf("\n");

/* à ajouter plus tard
    printf("Affichage largeur : \n");   
    print_bf(t); 
    printf("\n");
*/
/* NOTE : la mémoire n'est pas libérée ! à suivre */

    return 0;
}

Les affichages sont ils tous différents ? Sur une feuille dessinez l'arbre obtenu. Est-ce satisfaisant ?
Avant de continuer nous allons écrire la procédure de parcours en largeur

PARCOURS_LARGEUR(Arbre A)
    FIFO f
    enfiler A dans f
    TANT QUE f non vide :
        Arbre B = défiler f
        enfiler le fils gauche de B dans f 
        enfiler le fils droit de B dans f
        action sur B

Comme vous le voyez, cette fonction nécessite que nous disposions d'une librairie de FIFO. Voici le .h, à vous d'écrire le .c :

#ifndef _FIFO_H
#define _FIFO_H

typedef struct _cell{

    void * data;
    struct _cell * next;

}Cell;

typedef struct{
    Cell* first;
    Cell* last;
}Fifo;

int is_empty(Fifo);
Cell* create_cell(void *); /* contains a malloc */
void free_cell(Cell*); 
Fifo create_fifo();

/* return NULL if memory allocation issue */
Cell* fifo_add(Fifo*, void*);
void* fifo_get(Fifo*); /* call free_cell to free memory */

#endif

Vous pouvez maintenant programmer la fonction print_bf qui affiche l'arbre en le parcourant en largeur. Décommentez les lignes correspondantes dans le main() et testez.
téléchargez cette archive qui contient les fichiers ascii_bst.h et ascii_bst_xxb.o, ajoutez le .o qui correspond à votre architecture ¹ à votre unité de compilation puis ajoutez dans test.c un include de ascii_bst.h et un appel à la fonction print_ascii_art();.

Vous devriez obtenir la sortie :

dm@dellbookpro:~/sync/ens/4R-IN1/arbres_1$ ./a.out 
                                     001                                      
                  ____________________|___________________                   
                  ---                                    002                  
         __________|__________                  __________|__________         
        ---                 ---                 ---                 003        
    _____|______        _____|______        _____|______        _____|_____    
   ---       ---       ---       ---       ---       ---       ---       004   
 ___|___   ___|___   ___|___   ___|___   ___|___   ___|___   ___|___   ___|__  
---  ---  ---  ---  ---  ---  ---  ---  ---  ---  ---  ---  ---  ---  ---  005 

Affichage prefixé : 
 1  2  3  4  5 
Affichage infixé : 
 1  2  3  4  5 
Affichage postfixé : 
 5  4  3  2  1 
Affichage largeur : 
 1  2  3  4  5

Est-ce que cela correspond à ce que vous aviez dessiné ?

Comme on le voit l'arbre n'est pas équilibré du tout, et les performances seront donc équivalentes à celles d'une liste chainée toute simple (un peu dommage après le mal qu'on s'est donné)
Ajoutez les fonctions void rotate_right(AVL*); et void rotate_left(AVL*); dont le pseudo code est donné ci dessous :

arbre ROTATION_GAUCHE(arbre A) {
    arbre B
    B = fils droit de A
    le fils gauche de B devient le fils droit de A (A->d = B->g)
    A devient le fils gauche de B (B->g=A)
    retourne B
}

arbre ROTATION_DROITE(arbre A) {
    arbre B
    B = fils gauche de A
    le fils droit de B devient le fils gauche de A (A->g = B->d)
    A devient le fils droit de B (B->d=A)
    retourne B
}

Attention, même difficulté qu'au début du TP, ici on vous demande de faire des procédures en C qui prennent l'arbre par adresse, et non par copie (c'est pourquoi elles ne renvoient rien)

Testez ces fonctions en les appelant dans le main() sur la racine de l'arbre plusieurs fois de suite en ajoutant des appels à print_ascii_art() entre chaque appel
Avant d'aller plus loin, il nous manque la fonction de libération de la mémoire d'un arbre. Pour libérer la mémoire, il faut parcourir l'arbre et libérer tous les nœuds. Il faut le faire dans un ordre qui permette de ne pas se couper de la racine (si vous sciez une branche sur laquelle vous êtes assis dans un véritable arbre en bois, assurez vous d'être du bon côté !). Le parcours ici est donc le parcours postfix : les enfants d'abord, la racine en dernier. Ceci étant, nous n'aimons pas la duplication de code. Nous allons donc transformer nos quatre fonctions d'affichage en fonctions plus générique "visit" :
- void visit_prefix(BST t, void (*action)(BST*)); procédure récursive qui parcourt la racine puis le sous arbre gauche et enfin le sous arbre droit
- void visit_infix(BST t, void (*action)(BST*)); procédure récursive qui parcourt le sous arbre gauche puis la racine et enfin le sous arbre droit
- void visit_postfix(BST t, void (*action)(BST*)); procédure récursive qui parcourt le sous arbre gauche puis le sous arbre droit et enfin la racine
- void visit_bf(BST t, void (*action)(BST*)); procédure qui parcourt l'arbre en largeur
Les fonctions print précédentes deviennent :
```
void print_root(BST* t)
{
            printf(" %d ",*((*t)->data));
}
void print_prefix(BST t)
{ visit_prefix(t,&print_root); }

void print_infix(BST t)
{ visit_infix(t,&print_root); }

void print_postfix(BST t)
{ visit_postfix(t,&print_root); }

void print_bf(BST t)
{ visit_bf(t,&print_root); }
```
Remarquez que nous passons par adresse l'arbre a la fonction action, pour permettre à celle ci de le modifier. La fonction de libération de la mémoire occupée par notre ABR s'écrit alors :
```
void free_BST(BST * t)
{
    visit_postfix(*t,&free_node);
    *t=NULL;
}
```
il ne vous reste plus qu'à écrire la fonction void free_node(BST * t); qui libère la mémoire allouée dans create_node et qui remplace la valeur de t par NULL (c'est pour ca qu'on le passe par adresse).
BONUS : Ajoutez une enum visit_type avec les valeurs PREFIX, INFIX, POSTFIX, BF et modifiez le code pour n'avoir qu'une seule fonction visit qui prend en paramètre supplémentaire le type de visite souhaitée.

Arbres AVL¶

Les arbres AVL sont des BST particulier où les opérations d'insertions/délétions garantissent que la différence de hauteur entre les deux sous arbres droit et gauche est au plus 1. Ceci permet d'assurer d'être toujours dans le cas optimal lorsqu'on cherche un élément dans notre abre.

Pour se faire sans payer un cout mémoire ni CPU trop élevé, il faut stocker dans chaque noeud, en plus de la donnée, un entier "facteur d'équilibrage" ou en anglais "balance factor" égale à la hauteur du sous artbre droit moins la hauteur du sous arbre gauche. Cette valeur dans un arbre AVL ne peut valoir que -1 0 ou 1, et transitoirement -2 ou 2 lors de l'ajout ou la suppression d'un noeud. Elle peut donc être stockée sur 2bits. Nous utiliserons malgrès tout un int dans la suite pour simplifier.

Copiez votre répertoire tp4 dans un nouveau répertoire tp4_avl. Modifiez le nom des fichiers bst.c et bst.h en avl.c et avl.h, modifiez toutes les référence à BST en AVL, les types BSTNode en AVLNode etc etc. Téléchargez les fichiers ascii_avl.h et ascii_avl.o Testez, tout doit fonctionner comme précédemment avec les BST
Ajoutez un champs entier bf à la structure qui définie AVLNode
Modifiez la fonction create_node pour qu'elle initialise ce champs à 0 lors de la création d'un noeud.

Modification des fonctions de rotation (fe : facteur d'équilibrage):

arbre ROTATION_GAUCHE(arbre A) {
    arbre B
    int a,b

    B = fils droit de A
    a = fe de A
    b = fe de B

    le fils gauche de B devient le fils droit de A (A->d = B->g)
    A devient le fils gauche de B (B->g=A)

    fe de A devient a-max(b,0)-1
    fe de B devient min(a-2,a+b-2,b-1)

    retourne B
}

arbre ROTATION_DROITE(arbre A) {
    arbre B
    int a,b

    B = fils gauche de A
    a = fe de A
    b = fe de B

    le fils droit de B devient le fils gauche de A (A->g = B->d)
    A devient le fils droit de B (B->d=A)

    fe de A = a-min(b,0)+1
    fe de B = max(a+2,a+b+2,b+1)

    retourne B
}

Important : à l'aide d'un brouillon, vérifiez les calculs des facteurs d'équilibrage

Dans un AVL, un noeud est déséquilibré si sont facteur d'équilibrage est -2 ou 2. Cela ne peut se produire que sur la branche d'un noeud nouvellement ajouté. Nous allons écrire une fonction d'équilibrage void balance(AVL*); d'un noeud puis modifier la fonction d'insertion pour rémonter la branche sur laquelle l'ajout à lieu afin d'appeler la fonction d'équilibrage sur le premier noeud déséquilibré (il y en a au plus un). Les procédures sont données en pseudo code ci après

arbre EQUILIBRER(arbre A) {
    si fe de A == 2
        si fe du fils droit de A < 0
            remplacer fils droit de A par résultat de ROTATION_DROITE(fils droit de A)
        retourner le résultat de ROTATION_GAUCHE(A)

    si fe de A == -2
        si fe du fils gaucge de A > 0
            remplacer fils gauche de A par résultat de ROTATION_GAUCHE(fils gauche de A)
        retourner le résultat de ROTATION_DROITE(A)

La fonction ajouter renvoie maintenant la différence de hauteur produite par l'ajout, afin de pouvoir mettre à jour les facteurs d'équilibrage.

(arbre,entier) AJOUTER(element x, arbre A)
  entier h = 0

    si A est vide
        arbre B = creer un noeud avec l'element x
        A = B;
        renvoyer (A,1)

    sinon si x < racine de A
            (fils gauche de A,h) = AJOUTER(x,fils gauche de A)
            h = -h
    sinon si x > racine de A
            (fils droit de A,h) = AJOUTER(x,fils droit de A)

    si(h == 0) 
        renvoyer(A,0)

    fe de A = fe de A plus h
    A = EQUILIBRER(A)

    si fe de A == 0
        retourner (A,0)
    retourner (A,1)

Comme en C on ne peut renvoyer qu'une valeur, vous savez maintenant pourquoi depuis le début du TP nous passons les abres par leur adresse. Le prototype de la fonction add devient : int add(Elmt_t * data, AVL * t, int (*compare_elmt)(Elmt_t*, Elmt_t*));

Testez tout ca, et vérifiez dans votre main que les arbres produit par des ajouts successifs sont toujours équilibrés à l'aide de la fonction print_ascii_art
Bonus : ajoutez la fonction de suppression : pseudo code à chercher sur internet ! par exemple
- https://en.wikipedia.org/wiki/AVL_tree (page beaucoup plus étoffée que sa version francaise !)
- https://www.labri.fr/perso/maylis/ASDF/supports/notes/AVL.html
- https://igm.univ-mlv.fr/~mac/ENS/DOC/arbravl_7.pdf
- ...

32bits ou 64bits. ↩