TP4 — Arbres binaires de recherche¶

Objectifs¶

Ce TP prolonge les travaux sur les tableaux et les listes chaînées, piles et files. Vous allez construire une structure arborescente, observer les effets de l'ordre d'insertion, puis apprendre à maintenir l'arbre équilibré.

À la fin du TP, vous devrez savoir :

• représenter un arbre binaire de recherche (ABR) en C avec des pointeurs ;
• insérer et supprimer une valeur, et expliquer le rôle de la racine passée par adresse ;
• distinguer les parcours en profondeur et en largeur ;
• réutiliser une file FIFO pour parcourir un arbre en largeur ;
• expliquer pourquoi un ABR peut se dégrader en une structure linéaire ;
• réaliser une rotation gauche ou droite sans perdre de sous-arbre ;
• reconnaître les configurations qui nécessitent une rotation simple ou double.

Préparation et organisation du projet¶

Réutilisez le module elmt_t du TP précédent. Les valeurs seront comparées avec la fonction passée en paramètre ; l'arbre ne doit pas dépendre directement de la représentation d'un élément.

Créez un répertoire de travail pour le TP4 avec au minimum :

bst.h
bst.c
test_bst.c
Makefile

Commencez par le programme test_bst. La partie 5 précisera comment compléter ce même répertoire par une seconde implémentation et comment organiser le Makefile pour construire deux exécutables indépendants.

Compilez et testez après chaque fonction, plutôt que d'écrire toute la bibliothèque d'un seul coup.

Bibliothèque d'affichage ascii_art : téléchargement et préparation¶

Téléchargez dès maintenant l'archive ascii_avl_bst.tgz. Elle contient les en-têtes et objets précompilés de deux bibliothèques d'affichage : ascii_bst.h et ascii_bst pour les arbres binaires de recherche utilisés dans les parties 1 à 4 ; ascii_avl.h et ascii_avl pour la variante qui sera introduite en partie 5. Choisissez l'objet correspondant à votre architecture (32 ou 64 bits) et ne le liez qu'à l'exécutable qui utilise le type associé.

Vous utiliserez print_ascii_art() dès la partie 1.2, puis à nouveau pendant les rotations. Cette bibliothèque est un outil de visualisation.

Pour que l'objet précompilé utilisé dans les parties 1 à 4 reste compatible, conservez l'ordre des champs de BSTNode : data, ls, rs. Ne réordonnez pas la structure.

Partie 1 — Construire un arbre binaire de recherche¶

1.1 Définir les types et les invariants¶

Dans bst.h, définissez :

• BSTNode, structure contenant un pointeur Elmt_t *data, un pointeur BSTNode *ls vers le fils gauche et un pointeur BSTNode *rs vers le fils droit ;
• BST, alias de BSTNode *.

Un ABR doit respecter la propriété suivante pour chaque nœud : toutes les valeurs de son sous-arbre gauche sont strictement inférieures à sa valeur, et toutes celles du sous-arbre droit sont strictement supérieures. Cette propriété s'applique récursivement à tous les sous-arbres.

Pour ce TP, les nœuds conservent les pointeurs Elmt_t * fournis à l'insertion : l'arbre est propriétaire des nœuds BSTNode, mais pas des objets Elmt_t pointés par data. Les valeurs doivent donc rester valides tant que l'arbre les utilise. free_BST libérera les nœuds ; la libération des éléments appartient au code qui les a alloués.

Déclarez et implémentez les fonctions suivantes :

BST create_empty_BST(void);
int is_empty_bst(BST t);
int is_leaf(BSTNode *n);
BSTNode *create_node(Elmt_t *data);
void add(Elmt_t *data, BST *t,
         int (*compare_elmt)(Elmt_t *, Elmt_t *));

create_node alloue un nœud, initialise data avec le pointeur reçu et initialise ls et rs à NULL. Elle renvoie NULL si l'allocation échoue. add ignore une valeur déjà présente. Le paramètre BST *t permet de modifier la racine lorsque l'arbre est vide.

La fonction add¶

Pour ajouter un élément à un arbre, il faut d'abord trouver où il va. L'algorithme d'insertion consistre donc à chercher 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.

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

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.

1.2 Tester l'insertion et observer l'arbre¶

Au brouillon, dessinez les arbres obtenus si en partant d'un arbre vide on insère les valeurs :

4, 2, 6, 1, 3, 5, 7

1, 2, 3, 4, 5, 6, 7

Vérifiez vos arbres informatiquement en programmant ces séquences d'insertions puis en affichant les arbres obtenus avec la bibliothèque ascii_art. L'archive et les indications de liaison se trouvent dans la section « Bibliothèque d'affichage ascii_art : téléchargement et préparation » ci-dessus. Pour traiter cette partie, vous pouvez partir du squelette suivant :

#include "ascii_bst.h"
#include "bst.h"

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

    BST t1 = create_empty_BST();
    BST t2 = create_empty_BST();

    /* à modifier / compléter selon les exemples demandés */
    add(&n4,&t1,&compare_int);
    /* ... */
    print_ascii_art(t1);

    add(&n1,&t2,&compare_int);
    /* ... */
    print_ascii_art(t2);

/* NOTE : la mémoire n'est pas libérée ! à suivre */

    return 0;
}

Questions : obtenez-vous le même arbre ? Quelle est sa hauteur ? Combien de nœuds faut-il visiter pour rechercher la valeur 7 dans chaque arbre ?

Le démonstrateur ci-dessous permet de comparer les ordres d'insertion. Ne vous préoccupez pas des fonctions de rotation pour le moment.

1.3 Parcourir l'arbre en profondeur¶

Implémentez les trois parcours récursifs suivants :

void print_prefix(BST t);   /* racine, gauche, droite */
void print_infix(BST t);    /* gauche, racine, droite */
void print_postfix(BST t);  /* gauche, droite, racine */

Testez-les sur les deux arbres précédents.

À expliquer dans le compte rendu : pourquoi le parcours infixe d'un ABR affiche-t-il les valeurs dans l'ordre croissant ? Pourquoi les trois parcours peuvent-ils produire des sorties différentes pour un même arbre ?

Partie 2 — Parcourir l'arbre en largeur avec la FIFO du TP3¶

Un parcours en largeur visite les nœuds niveau après niveau, de gauche à droite. Avant de lire la suite, avez vous une idée de comment faire ?

La réponse consiste à utiliser une file FIFO : on enfile les enfants d'un nœud, puis on traite les nœuds dans l'ordre où ils ont été ajoutés à la file.

Le principe est le suivant :

si l'arbre est vide : terminer
créer une file vide
enfiler la racine
 tant que la file n'est pas vide :
     n ← défiler la file
     traiter n
     si n possède un fils gauche : l'enfiler
     si n possède un fils droit : l'enfiler

En vous basant sur l'implémentation de FIFO du TP3 réécrivez une bibliothèque plus générique dont voici le .h :

#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

La file doit pouvoir contenir des pointeurs vers des BSTNode, et fifo_get doit libérer uniquement la cellule interne de la file, pas le nœud de l'arbre renvoyé.

Écrivez puis testez :

void print_breadth_first(BST t);

Vérifiez le résultat avec l'arbre équilibré et l'arbre obtenu en insérant des valeurs triées. Expliquez pourquoi le parcours en largeur dépend de l'ordre d'insertion, mais respecte toujours l'ordre des niveaux de l'arbre obtenu. La fonction est appelée print_breadth_first dans ce sujet pour que son rôle soit immédiatement compréhensible.

Partie 3 — Pourquoi et comment équilibrer un ABR ? Les rotations¶

Pour un arbre de hauteur h, une recherche ou une insertion suit un chemin de longueur au plus proportionnelle à h.

• Dans un arbre bien équilibré, la hauteur est de l'ordre de log2(n) et les opérations de recherche sont en O(log n).
• Dans un arbre dégénéré, la hauteur peut atteindre n - 1 et les opérations deviennent en O(n).

Vous avez du constater vous même cette différence lors de l'exercice précédant, lorsqu'on vous a demandé de compter les comparaisons effectuées pour construire les arbres.

La propriété ABR maintient l'ordre, mais elle ne garantit pas une bonne hauteur. C'est précisément ce que l'on a observé en insérant les valeurs triées.

3.1 Rotation droite et rotation gauche¶

Dans cette partie, revenez au démonstrateur ABR de la partie 1.2. Il ne rééquilibre jamais l'arbre à votre place : vous devez décider où intervenir et quelle rotation appliquer. Les boutons de préparation créent les arbres de départ.

Une rotation modifie localement les liens entre une racine, son pivot et leurs sous-arbres. Elle doit préserver la propriété ABR : l'ordre infixe des valeurs reste identique avant et après la rotation.

Pour une rotation droite, le fils gauche devient la nouvelle racine du sous-arbre. Le sous-arbre droit de ce pivot devient le fils gauche de l'ancienne racine, laquelle devient le fils droit du pivot. Pour une rotation gauche, on effectue l'opération symétrique avec le fils droit.

Voici les deux algorithmes à traduire en C. Ils supposent que le fils utilisé comme pivot existe ; vous pouvez conserver cette précondition ou protéger les fonctions contre un appel invalide.

Rotation droite

arbre ROTATION_DROITE(arbre A) {
    arbre B ← fils gauche de A
    A->ls ← B->rs (le fils droit de B devient le fils gauche de A)
    B->rs ← A (A devient le fils droit de B)
    retourne B
}

Rotation gauche

arbre ROTATION_GAUCHE(arbre A):
    arbre B ← fils droit de A
    A->rs ← B->ls (le fils gauche de B devient le fils droit de A)
    B->ls ← A (A devient le fils gauche de B)
    retourne B

Dans la version ABR, implémentez les fonctions suivantes dans bst.c :

void rotate_right(BST *t);
void rotate_left(BST *t);

Le paramètre t est l'adresse du pointeur qui désigne la racine du sous-arbre à tourner. Il ne suffit donc pas de modifier les liens des nœuds : il faut aussi mettre à jour *t pour désigner le nouveau pivot. Traduisez les algorithmes ci-dessus en C sans perdre le sous-arbre transféré.

Après chaque rotation :

1. affichez l'arbre avec ascii_art ;
2. vérifiez que tous les nœuds sont toujours accessibles exactement une fois ;
3. vérifiez que le parcours infixe est inchangé ;
4. vérifiez que le pointeur vers la racine du sous-arbre désigne bien le nouveau pivot.

3.2 Déduire les rotations à partir des quatre configurations¶

Utilisez le démonstrateur ABR. Préparez successivement les séquences LL, RR, LR et RL. Pour chaque cas, avancez en mode pas à pas, puis choisissez vous-même les rotations. Les cases du tableau ne se remplissent qu'après vos essais : indiquez les rotations dans l'ordre réel où vous les exécutez et la racine finale. Le bouton de correction colore chaque réponse en vert ou en rouge.

Vérification complémentaire — rotation sur un sous-arbre interne. Réinitialisez le démonstrateur puis insérez 50, 30, 70, 20, 40, 60, 80. Sélectionnez le nœud 30 et effectuez une rotation droite. La racine globale doit rester 50, mais la racine de son sous-arbre gauche change. Expliquez pourquoi il faut passer l'adresse du pointeur vers ce sous-arbre et vérifiez que le parcours infixe reste 20, 30, 40, 50, 60, 70, 80.

La partie 4 introduira une variante qui choisit elle-même les rotations. Vous pourrez alors comparer son comportement avec vos choix manuels.

Partie 4 — Transformer l'ABR en AVL¶

Un AVL est un ABR qui maintient une différence de hauteur entre sous-arbres gauche et droit comprise entre -1 et +1 pour chaque nœud.

On stocke dans chaque nœud le facteur d'équilibrage :

bf = hauteur(sous-arbre droit) - hauteur(sous-arbre gauche)

Ajoutez un champ int bf à la fin de la structure AVLNode, après data, ls et rs. Initialisez-le à zéro dans create_node. Pour un nœud AVL équilibré, bf vaut -1, 0 ou +1. Lorsqu'une insertion modifie une hauteur, un facteur peut temporairement atteindre -2 ou +2 : il faut alors rééquilibrer.

Le démonstrateur AVL ci-dessous reprend les mêmes opérations, mais il affiche maintenant le facteur bf de chaque nœud et applique automatiquement les rotations nécessaires. Il permet aussi de supprimer une valeur : observez alors la remontée vers la racine, car une suppression peut nécessiter plusieurs rééquilibrages successifs. Les deux modes — automatique et pas à pas — restent disponibles.

4.1 Réimplémenter les rotations en mettant à jour les facteurs¶

Dans avl.h, définissez AVLNode avec les champs data, ls, rs, bf, dans cet ordre, puis AVL comme pointeur vers AVLNode. Pour l'affichage, utilisez ascii_avl.h et l'objet précompilé correspondant, contenus dans l'archive téléchargée en préparation ; ne liez pas l'objet ascii_bst à l'exécutable AVL. L'ordre des champs data, ls, rs, puis bf est imposé par la bibliothèque d'affichage. Dans avl.c, reprenez les rotations de la partie précédente avec les signatures void rotate_right(AVL *t); et void rotate_left(AVL *t);.

Avant d'étudier les formules, relevez les facteurs d'équilibrage dans le tableau interactif ci-dessous.

Dans chaque ligne, A désigne l'ancienne racine du sous-arbre que l'on tourne et B le pivot qui devient la nouvelle racine de ce sous-arbre. Pour une rotation double, traitez séparément la première et la seconde rotation. Utilisez le démonstrateur AVL en mode Pas à pas ; entre les essais, réinitialisez l'arbre ou choisissez une autre démonstration. Pour le dernier essai, réinitialisez l'arbre, insérez successivement 4, 2, 5, 1, 3, puis supprimez 5. Saisissez les facteurs dans les quatre colonnes, puis cliquez sur « Vérifier les relevés ». Le signe + est facultatif pour les valeurs positives.

Remarquez que les facteurs après rotation ne sont pas nécessairement tous nuls : la suppression peut laisser un facteur +1 sur la nouvelle racine et -1 sur l'ancienne.

À partir de vos essais, proposer les formules pour calculer les nouveaux 'balance factor' des noeuds lorsqu'on fait des rotations. Noter a le facteur de l'ancienne racine A et b celui du pivot B. Quels sont les nouveaux 'balance factor' de l'ancienne racine et du pivot après une rotation gauche ? après une rotation droite ? (en fonction de 'a' et de 'b').

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

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

Les fonctions min et max ci-dessus désignent les minimum et maximum de leurs arguments. Il faut mémoriser a et b avant de modifier les facteurs ou les pointeurs. Pour la rotation gauche, B est l'ancien fils droit de A ; pour la rotation droite, B est l'ancien fils gauche.

Préparer la fonction balance : compléter le tableau¶

Les quatre cas classiques d'insertion sont bien LL, LR, RR et RL. Le nom décrit le chemin suivi depuis le premier nœud déséquilibré jusqu'au nœud inséré : LL signifie gauche puis gauche ; LR, gauche puis droite ; RR, droite puis droite ; RL, droite puis gauche.

À l'aide de votre programme ou du démonstrateur vu plus haut, remplissez le tableau ci-dessous qui porte donc sur les quatre configurations d'insertion, auxquelles on ajoute deux cas importants pour la suppression : après une suppression, le fils du nœud déséquilibré peut avoir bf == 0. Remplissez le tableau avant de cliquer sur « Vérifier les réponses » ; le script colore chaque cellule et compte les réponses correctes.

si (*t)->bf == -2 :
    si (*t)->ls->bf > 0 :
        rotation gauche sur le fils gauche
    rotation droite sur *t
sinon si (*t)->bf == +2 :
    si (*t)->rs->bf < 0 :
        rotation droite sur le fils droit
    rotation gauche sur *t

Implémentez ensuite la fonction suivante :

void balance(AVL *t);

Testez-la d'abord avec les quatre séquences d'insertion du tableau, puis avec les exemples de suppression. Dans le simulateur, contrôlez non seulement le résultat final, mais aussi l'ordre des rotations indiquées dans le journal.

4.2 Adapter l'insertion¶

L'insertion AVL remonte le chemin parcouru et met à jour les facteurs d'équilibrage. Elle communique si la hauteur du sous-arbre a changé, afin de ne pas recalculer toutes les hauteurs à chaque nœud.

Utilisez le prototype suivant :

int add(Elmt_t *data, AVL *t,
        int (*compare_elmt)(Elmt_t *, Elmt_t *));

Convention de retour : 1 indique que la hauteur du sous-arbre a augmenté, 0 qu'elle n'a pas augmenté (valeur déjà présente comprise), et -1 une erreur d'allocation.

Le principe récursif à traduire en C est le suivant :

AJOUTER(x, A):
    si A est vide:
        créer un nœud contenant x
        si l'allocation échoue: retourner -1
        retourner 1

    comparer x à la valeur de A
    si x est déjà présent: retourner 0

    si x < A.data:
        delta = AJOUTER(x, A.gauche)
        si delta <= 0: retourner delta
        A.bf = A.bf - 1
    sinon:
        delta = AJOUTER(x, A.droite)
        si delta <= 0: retourner delta
        A.bf = A.bf + 1

    si A.bf == 0: retourner 0
    si A.bf == -1 ou A.bf == +1: retourner 1
    équilibrer le sous-arbre enraciné en A
    retourner 0

Ce pseudo-code suppose que balance rétablit un AVL en cas de facteur -2 ou +2, et que les rotations mettent à jour les facteurs. Lors de la remontée récursive, assurez-vous que le lien vers le sous-arbre éventuellement ré-enraciné est bien conservé. Le facteur d'équilibrage est défini ici comme hauteur droite moins hauteur gauche : ne mélangez pas cette convention avec la convention inverse.

5.3 Étendre l'AVL à la suppression¶

Le démonstrateur permet de supprimer des valeurs. Dans votre bibliothèque C, réalisez également cette opération si le temps du TP le permet ; elle constitue un excellent exercice de réutilisation des rotations déjà écrites.

Vous pouvez utiliser le prototype suivant :

int delete_avl(Elmt_t *key, AVL *t,
               int (*compare_elmt)(Elmt_t *, Elmt_t *));

La fonction renvoie 1 si un élément a été supprimé et 0 si la clé était absente. Elle libère le nœud AVLNode retiré, mais ne libère pas l'objet Elmt_t *data, conformément au contrat de propriété établi au début du sujet. N'appelez pas cette fonction remove, nom déjà utilisé par la bibliothèque standard C.

Traitez les trois situations classiques : nœud feuille, nœud ayant un seul fils, nœud ayant deux fils. Dans le dernier cas, remplacez sa valeur par celle de son successeur infixe (le minimum du sous-arbre droit), puis retirez le nœud successeur. Dans tous les cas, remontez jusqu'à la racine pour mettre à jour les facteurs et rééquilibrer les sous-arbres concernés. Contrairement à l'insertion, une suppression peut faire diminuer la hauteur de plusieurs sous-arbres successifs : ne vous arrêtez pas nécessairement après la première rotation.

Dans le simulateur, essayez notamment de supprimer une feuille, un nœud avec un seul fils, un nœud avec deux fils, puis la racine. Après chaque suppression, vérifiez le parcours infixe, les facteurs bf et les éventuelles rotations.

5.4 Jeux de tests obligatoires¶

Testez au minimum les quatre séquences suivantes ; chacune doit conduire à une racine de valeur 20 après le troisième ajout :

Ajoutez des tests avec des valeurs déjà présentes, des valeurs croissantes, décroissantes et un arbre déjà équilibré. Vérifiez que :

• le parcours infixe donne les valeurs en ordre croissant ;
• aucun nœud n'est perdu ou relié deux fois ;
• tous les facteurs d'équilibrage finaux appartiennent à {-1, 0, +1} ;
• la hauteur reste logarithmique sur de grandes séquences d'insertion triées.

Partie 6 — Parcours génériques et libération mémoire¶

Pour éviter de dupliquer la logique de parcours, remplacez les affichages spécialisés par des fonctions visit qui prennent une action en paramètre. L'action reçoit un pointeur vers le nœud à visiter ; elle ne modifie pas la structure de l'arbre.

void visit_prefix(BST t, void (*action)(BSTNode *));
void visit_infix(BST t, void (*action)(BSTNode *));
void visit_postfix(BST t, void (*action)(BSTNode *));
void visit_breadth_first(BST t, void (*action)(BSTNode *));

Les fonctions print_prefix, print_infix, print_postfix et print_breadth_first deviennent de simples wrappers autour de ces parcours et d'une action d'affichage, par exemple print_root(BSTNode *n).

Implémentez ensuite free_BST(BST *t) avec une fonction récursive spécifique. La mémoire des nœuds doit être libérée en postfixe : on libère les sous-arbres gauche et droit avant leur parent. Le pointeur vers la racine fourni par adresse doit être remis à NULL. N'utilisez pas directement l'action générique de visite pour libérer les nœuds : comme elle ne reçoit qu'un pointeur vers le nœud, elle ne peut pas remettre à jour le lien du parent. Rappelez-vous que, selon le contrat établi au début du TP, les objets Elmt_t ne sont pas libérés par free_BST.

Bonus¶

• Définir un enum visit_type avec les valeurs PREFIX, INFIX, POSTFIX et BREADTH_FIRST, puis factoriser les parcours dans une seule fonction visit.
• Ajouter une fonction de vérification qui calcule les hauteurs et confirme récursivement que la propriété AVL est respectée.
• Comparer la hauteur d'un ABR construit avec une séquence triée et celle de l'AVL construit avec la même séquence.

Compte rendu¶

Votre compte rendu doit répondre aux questions suivantes :

1. Pourquoi un ABR peut-il avoir des opérations en O(n) malgré sa propriété d'ordre ?
2. Pourquoi le parcours infixe d'un ABR renvoie-t-il les valeurs triées ?
3. En quoi le passage de la racine par adresse est-il essentiel aux rotations ?
4. Pourquoi une rotation préserve-t-elle la propriété ABR ?
5. Quelles différences observez-vous entre les cas LL, RR, LR et RL ?
6. Pourquoi le facteur d'équilibrage stocké évite-t-il de recalculer les hauteurs complètes à chaque insertion ?
7. Quels invariants vérifiez-vous pour vous assurer que votre AVL reste correct ?

Le rendu doit inclure les fichiers source, le Makefile, les tests, ainsi que quelques sorties ascii_art avant et après rotation pour les quatre cas AVL.