Organisation (2 pts)

Le TP se réalise en groupes de 2 à 3 étudiant(e)s. L’objectif est que chaque groupe produise un code propre, versionné, et relise le travail avec les autres membres du groupe (relectures croisées, pair-programming, etc.). L’idée étant de partager la connaissance et gagner en vélocité de travail.

Chaque groupe doit :

• créer un dépôt Git dédié au TP (sur GitHub)
• ajouter tous les membres du groupe comme collaborateurs du dépôt plus le professeur.
• organiser le projet au minimum avec :
• un répertoire src/ pour le code C, donc les fichiers .c et .h
• éventuellement un répertoire tests/ pour vos jeux de tests (bonus éventuel)
• utiliser des messages de commit explicites (un commit = une idée / un ensemble cohérent de modifications)
• pas de gros commit : si je voie un fichier en entier trop parfait alors est-ce une IA ?
• Norme IETF RFC 1149 proscrite, pas de retard autorisé

Un seul dépôt par groupe est attendu. Le nom du dépôt doit contenir clairement l’identifiant du cours et les noms des membres du groupe (par exemple : tp-data-struct-bst-avl-btree_nom1_nom2_nom3 donc quand votre professeur clone il n’a pas a chercher qui a fait quoi et où !

FIFO et LIFO (7 pts)

On s’intéresse ici, à la différence de comportement entre une structure qui traite les éléments dans l’ordre d’arrivée (FIFO) et une structure qui les traite dans l’ordre inverse (LIFO), à travers de petits exercices. L’idée est de voir comment le choix de politique d’ordonnancement impacte directement la séquence d’éléments effectivement manipulée, ce qui sera utile lorsque l’on raisonne sur les parcours d’arbres et sur l’évaluation d’expressions : tout du moin c’est une possibilité pour l’implémentation.

Insertion de 1, 2, 3, 4, 5 (3 pts)

On dispose d’une structure abstraite S dans laquelle on peut :

• insérer un entier avec push(x)
• retirer un entier avec pop() et afficher la valeur retirée

On va comparer deux comportements possibles de S : une politique LIFO (pile) et une politique FIFO (file).
On effectue successivement les opérations :

• push(1)
• push(2)
• push(3)
• push(4)
• push(5)

Puis on applique cinq fois pop() en affichant à chaque fois la valeur retirée.

1. Donnez la séquence de valeurs affichées si S se comporte comme une pile (LIFO).
2. Donnez la séquence de valeurs affichées si S se comporte comme une file (FIFO).
3. Que ce passe t’il si on inverse les opérations de push ? 5, 4, 3, 2, 1 ?

Évaluation d’expression (4 pts)

On considère maintenant l’évaluation d’expressions arithmétiques en notation polonaise (préfixe) et en notation polonaise inversée (postfixe). Ces notations ont la particularité de supprimer les parenthèses au profit d’un ordre d’écriture des opérateurs et opérandes qui se prête particulièrement bien à une évaluation à l’aide d’une structure de type pile (LIFO) ou file (FIFO) en fonction de l’ordre.

On se concentre ici sur la notation postfixée (Reverse Polish Notation), où chaque opérateur apparaît après ses deux opérandes, par exemple :

• notation classique : infixe : 3 + 4
• notation polonaise inversé : postfixe : 3 4 +

1. Donner la séquence d’opérations sur une pile (push/pop) permettant d’évaluer une expression postfixe composée des opérateurs +, -, *, / et d’opérandes entiers positifs. On suppose que l’expression est correcte implicitement. (1 pt)
2. Appliquer cette méthode d’évaluation à l’expression postfixe suivante (1 pt) :
   • 3 4 + 2 * (qui correspond en infixe à (3 + 4) * 2)
   • En détaillant : le contenu de la pile après chaque lecture de symbole,
   • En détaillant : les opérations effectuées lors de la rencontre d’un opérateur.
3. Proposer une fonction C de signature : int eval_postfix(const char *expr); (2 pt)
4. Vous pouvez vous aidez de l’exo-3 en C token, mais surtout expliquez la différence en complexité spatial vs une solution IA utilisant malloc pour le split des tokens (bonus 4 pts)

BST (26 pts)

On considère la structure suivante pour représenter un Binary Search Tree (BST) :

struct tree_node {
  int data; // ou int key + void* data;
  struct tree_node *parent;
  struct tree_node *left;
  struct tree_node *right;
};

typedef struct tree_node TreeNode;

typedef void (*process_fn)(struct tree_node *);

Un BST est un arbre binaire dans lequel, pour chaque nœud x, toutes les valeurs du sous‑arbre gauche sont strictement inférieures à x->data, et toutes les valeurs du sous‑arbre droit sont strictement supérieures. Cette contrainte locale impose un ordre global sur les clés et permet d’implémenter des opérations de recherche, insertion et suppression dont le coût dépend principalement de la hauteur de l’arbre. La topologie de l’arbre reflète directement l’ordre d’insertion, ce qui explique pourquoi des mécanismes de rééquilibrage seront nécessaires plus loin (AVL).

Proposer trois arbres (1.5 pts)

1. un arbre dit équilibré
2. un arbre dit non équilibré
3. un arbre dit dégénéré

Main de base avec arbre statique (2.5 pt)

Arbre construit statiquement :

TreeNode root = {
  .data = 'F',
  .left = &(TreeNode){
    .data = 'B',
    .left = &(TreeNode){ .data = 'A', .left = NULL, .right = NULL, },
    .right = &(TreeNode){
      .data = 'D',
      .left = &(TreeNode){ .data = 'C', .left = NULL, .right = NULL, },
      .right = &(TreeNode){ .data = 'E', .left = NULL, .right = NULL, },
    },
  },
  .right = &(Node){
    .data = 'G',
    .left = NULL,
    .right = &(TreeNode){
      .data = 'I',
      .left = &(TreeNode){ .data = 'H', .left = NULL, .right = NULL, },
      .right = NULL,
    },
  },
};

1. Questions : Expliquer en quoi cette construction « sur la pile » est limitée dès qu’on souhaite insérer ou supprimer des nœuds à l’exécution. Et si cette construction est compatible avec malloc et free (1 pt)
2. Ecrire un main de base qui déclare cette variable root pour la suite (0.5 pt)
3. Est-ce un BST en suposant l’ordre alphabétique ? (1 pt)

Fonctions de traversée d’arbre récursives (2.5 pts)

On veut implémenter les trois parcours avec un callback générique :

typedef void (*process_fn)(struct tree_node *);

Cette abstraction permet d’utiliser les mêmes fonctions de parcours pour des usages variés : affichage, libération mémoire, mise à jour de champs auxiliaires, instrumentation, etc. L’idée est de séparer la logique de navigation dans l’arbre de la logique de traitement des nœuds.

Base à corriger/compléter :

// Préfixe (preorder) : Nœud → Gauche → Droite
void preorder(struct tree_node *n, process_fn process) {
  // process left right;
}

// Infixe (inorder) : Gauche → Nœud → Droite
void inorder(struct tree_node *n, process_fn process) {
  if (!n) return;
  // left process right;
}

// Postfixe (postorder) : Gauche → Droite → Nœud
void postorder(struct tree_node *n, process_fn process) {
  if (!n) return;
  // left right process
}

Questions :

1. Adapter ces fonctions pour utiliser correctement process_fn (signatures, appels). (1 pt)
2. Écrire un callback void print_node(struct tree_node *n) qui affiche n->data. (1 pt)
3. Que donne le parcours infixe sur l’arbre précédent ? (0.5 pt)

Transformer en allocation dynamique (5 pts)

L’arbre précédent est sur la pile, ce qui impose une durée de vie couplée à celle de la fonction qui le définit. Pour un BST réellement dynamique, il faut allouer les nœuds sur le tas avec malloc et les libérer explicitement avec free. Cette maîtrise fine de la durée de vie est une condition nécessaire pour des opérations robustes de modification de la structure.

Pour la suite, on construira un BST à la main en insérant successivement les valeurs :

10, 2, 25, 15, 30, 12, 20, 16, 24, 17, 22

1. Construire à la main le BST résultant de cette séquence d’insertions et dessiner l’arbre (pointeurs left et right). (1 pt)
2. Quel aurait été le résultat si la séquence initial avait été trié ? (1 pt)
3. Écrire : struct tree_node *node_new(int data); qui alloue un nœud sur le tas, initialise data, puis met left, right, parent à zero / null. (1 pts)
4. Écrire : struct tree_node *bst_insert(struct tree_node **root, int data); qui insère data dans le BST, met à jour parent, et renvoie le nœud inséré. (2 pts)

Fonctions de traversée d’arbre itératives (5 pts)

Contraintes :

• Parcours itératif (pas de récursion).
• Aucune pile explicite, aucun champ supplémentaire dans struct tree_node.
• Utilisation autorisée de parent et de == pour comparer des adresses.
• Utilisé un callback pour le traitement (process_fn)

Questions :

1. Proposer une version itérative de preorder respectant ces contraintes. (2 pts)
2. Proposer une version itérative de inorder respectant ces contraintes. (2 pts)
3. Expliquer en quelques phrases la stratégie générale de votre solution (sans rentrer dans chaque ligne de code). (1 pt)
4. Comparer la complexité sptial et temporel avec les versions récursives. (bonus 4 pts)

Mettre en œuvre tree_free (2.5 pts)

Une fois que les nœuds sont alloués dynamiquement, il faut prévoir un mécanisme pour libérer tout ou partie de l’arbre. L’approche naturelle consiste à utiliser un parcours postfixe, de manière à libérer d’abord les sous‑arbres puis le nœud courant. Vous devez donc écrire la fonction void tree_free(struct tree_node *subroot); qui libère tout le sous‑arbre enraciné en subroot, utilisé les fonctions de parcours d’arbre précédement définies (2.5 pts)

Mettre en œuvre tree_delete (4 pts)

On souhaite maintenant supprimer des clés dans le BST d’entiers.

Spécification :

struct tree_node *tree_delete(struct tree_node **root, int key);
// retourne NULL si la clé n'est pas trouvée

1. Implémenter tree_delete en gérant les trois cas : (2 pts)
   • nœud sans enfant,
   • nœud avec un seul enfant,
   • nœud avec deux enfants : utiliser le successeur comme nœud de remplacement. (Le plus petit élément strictement supérieur à N. Dit autrement le minimum de l’arbre de droite).
2. Sur le BST de référence, dessiner l’arbre après : (1 pt)
   • tree_delete(&root, 24),
   • puis tree_delete(&root, 15) (en partant du résultat précédent).
3. Tester expérimentalement différentes combinaisons : (1 pt)
   • supprimer x puis y,
   • supprimer y puis x.
   • Discuter si l’opération est commutative du point de vue de la structure résultante de l’arbre.

Variante de tree_delete avec prédécesseur (3 pts)

Lorsque le nœud à supprimer possède deux enfants, on peut choisir de le remplacer par son prédécesseur au lieu de son successeur. Ce choix local induit un réarrangement globalement différent de l’arbre, mais toujours valide du point de vue de l’invariant BST.

Questions :

1. Modifier tree_delete pour qu’elle utilise le prédécesseur comme nœud de remplacement dans le cas « deux enfants ». (1 pt)
2. Appliquer successivement les opérations : suppression de 25, puis de 20, puis de 10, avec la version successeur et la version prédécesseur. Comparer les structures obtenues (par exemple en termes de hauteur ou d’« équilibrage » visuel). (1 pt)
3. Proposer une version de tree_delete qui choisit aléatoirement, pour chaque suppression de nœud à deux enfants, entre successeur et prédécesseur. Discuter l’intérêt de cette randomisation du point de vue de la forme moyenne de l’arbre. (1 pt)

Arbres AVL (15 pts)

Les arbres AVL sont des BST munis d’une contrainte supplémentaire sur la hauteur relative des sous‑arbres : pour chaque nœud, la différence de hauteur entre le sous‑arbre gauche et le sous‑arbre droit est au plus 1. Cette contrainte locale garantit une hauteur globale logarithmique en fonction du nombre de nœuds, ce qui stabilise la complexité des opérations.

On considère :

typedef struct avl_node {
  int key;
  int height;
    void *data; // inutile dans le TP
  struct avl_node *left;
  struct avl_node *right;
  struct avl_node *parent;
} avl_node;

Questions (6 pts)

1. Les deux arbres construits dans la partie BST (entiers et lettres) satisfont‑ils la condition AVL ? Justifier votre réponse.
2. Si ce n’est pas le cas, proposer une nouvelle version équilibrée contenant les mêmes clés.
3. Montrer qu’un AVL contenant $n$ nœuds a une hauteur en $O(\log n)$.
4. Préciser si l’on parle de $\log_2(n)$ ou $\log_{10}(n)$
5. Pourquoi cette distinction n’affecte pas la classe de complexité et que l’on parle simplement de $O(\log n)$.
6. Justifier que avl_insert a une complexité en $O(\log n)$ et effectue un nombre $O(1)$ de rotations par insertion.

Rotations (7 pts)

Après une insertion ou une suppression locale, il peut être nécessaire de rétablir la propriété AVL autour d’un nœud x en effectuant des rotations.

1. Décrire les quatre cas classiques de rotation (LL, RR, LR, RL), en explicitant les préconditions sur les facteurs d’équilibre des nœuds impliqués. (2 pt)
2. Discuter pourquoi, pour une insertion donnée, le nombre total de rotations nécessaires est borné par une constante indépendante de la taille de l’arbre. (1 pt)
3. Écrire la fonction : avl_node *avl_balance(avl_node *x);, (4 pts)

Fonction avl_insert(x) (2 pts)

L’insertion dans un AVL suit la logique d’insertion dans un BST, puis opère un rééquilibrage le long du chemin de remontée. Écrire la fonction :avl_node *avl_insert(avl_node *root, avl_node *x); en supposant left(x) = right(x) = parent(x) = NULL au départ. Avec une stratégie pour avl_insert, qui insère le nœud comme dans un BST (facile) puis remonte et appelle avl_balance sur les nœuds concernés. (2 pts)

B‑Tree (8 pts)

Les B‑Trees généralisent les arbres de recherche à des nœuds contenant plusieurs clés et plusieurs pointeurs enfants, afin de minimiser la hauteur de l’arbre et le nombre d’accès à des blocs mémoire. Un B‑Tree de degré minimum $t$ impose que chaque nœud (sauf la racine) contienne entre $t-1$ et $2t-1$ clés, et que toutes les feuilles soient à la même profondeur.

Construction pour ALGORITHMS, t = 3 (2 pts)

1. Construire le B‑Tree de degré minimum $t = 3$ résultant de l’insertion successive des lettres :
   `A L G O R I T H M S.
2. Détailler les éclatements (splits) de nœuds et la remontée des clés médianes lors des insertions.

Nombre de clés et hauteur (2 pts)

1. Donner, en fonction de $t$ et de la hauteur $h$, une expression du nombre maximal de clés que peut contenir un B‑Tree.
2. Discuter le lien entre : nombre minimal de clés et hauteur maximale pour un nombre donné de clés $n$.

Recherche et complexité (2 pts)

On suppose que, dans chaque nœud, la recherche de la clé se fait par recherche dichotomique (les clés sont triées).

1. Montrer que la complexité de btree_search est en $O(\log n)$, en explicitant la contribution de : la hauteur de l’arbre et la recherche interne dans un nœud.
2. Discuter pourquoi cette complexité est asymptotiquement indépendante du paramètre $t$, même si $t$ a un impact important sur les constantes.

Minimum, prédécesseur et suppression (4 pts)

Questions :

1. Expliquer comment trouver la clé de valeur minimum dans un B‑Tree. (2 pts)
2. Expliquer comment trouver le prédécesseur d’une clé dans un B‑Tree, en distinguant les cas où (2 pts) : la clé possède un sous‑arbre gauche et la clé se trouve dans une feuille.

Bonus (40 pts)

Proposer une structure en C permettant de représenter un nœud de B-tree (tableaux de clés, pointeurs vers les enfants, compteur de clés), puis écrire un programme fonctionnel illustrant son utilisation. MAIS Démontrez que ce n’est pas codé par une IA. ;)