Structures de données : piles, files, arbres et tas

Quelle est la règle de fonctionnement d'une pile (stack) ?

Une pile suit la règle LIFO (Last In, First Out) : on ne peut accéder/retirer qu'au sommet, qui est le dernier élément empilé.

Vrai ou faux : dans un arbre binaire de recherche (ABR), toutes les valeurs du sous-arbre gauche d'un nœud sont inférieures à la valeur de ce nœud.

Vrai. C'est exactement la propriété définissante d'un ABR, qui garantit que la recherche peut se faire en suivant un unique chemin de la racine à la feuille, comme une dichotomie sur un arbre.

Dans un tas-min, où se trouve toujours l'élément minimal ?

Par la propriété de tas-min (chaque nœud $\leq$ ses enfants), le minimum global se trouve nécessairement à la racine.

Vrai ou faux : dans un tas représenté par un tableau (indexation à partir de 0), l'enfant gauche du nœud d'indice $i$ se trouve à l'indice $2i+1$.

Vrai. C'est la formule standard de représentation d'un tas par tableau : enfant gauche à $2i+1$, enfant droit à $2i+2$, parent à $\lfloor(i-1)/2\rfloor$.

Quelle est la complexité moyenne de la recherche d'une clé dans une table de hachage bien conçue ?

Avec une bonne fonction de hachage répartissant uniformément les clés, le nombre moyen de collisions par case reste constant, donc la recherche se fait en temps constant en moyenne — même si le pire cas reste $O(n)$.

Un arbre binaire de recherche est construit en insérant successivement $1,2,3,4,5$ (déjà triés). Quelle est sa hauteur, et pourquoi ?

Comme les valeurs sont insérées dans l'ordre croissant, chaque nouvelle valeur est toujours supérieure à toutes les précédentes : elle devient l'enfant droit du dernier nœud inséré. L'arbre dégénère en une « liste chaînée » de hauteur $n-1=4$.

Pourquoi les arbres AVL ou rouge-noir garantissent-ils $O(\log n)$ pour les opérations de base, contrairement à un ABR naïf ?

Les arbres équilibrés effectuent des rotations locales après chaque insertion/suppression pour garantir que la hauteur reste $O(\log n)$ même dans le pire cas, contrairement à un ABR naïf qui peut dégénérer en hauteur $O(n)$.

Pour insérer un élément dans un tas-min de taille $n$ (le tas étant un tableau), quelle est la complexité de l'opération ?

On ajoute l'élément en fin de tableau ($O(1)$), puis on le fait remonter (percolation) le long d'un chemin de la feuille à la racine, dont la longueur est au plus la hauteur du tas, soit $O(\log n)$ (un tas est toujours quasi-complet, donc sa hauteur est $\Theta(\log n)$).

Vrai ou faux : une file (queue) FIFO est adaptée pour implémenter un parcours en largeur (BFS) d'un graphe.

Vrai. Le parcours en largeur explore les sommets niveau par niveau ; en enfilant les voisins découverts et en défilant dans l'ordre de découverte (FIFO), on garantit que tous les sommets d'un niveau sont traités avant ceux du niveau suivant.

Combien de comparaisons au minimum (dans le pire cas) sont nécessaires pour trouver le minimum d'un tableau non trié de $n$ éléments, et pourquoi ne peut-on pas faire mieux ?

Borne supérieure ($n-1$ comparaisons suffisent). Un algorithme simple parcourt le tableau en gardant en mémoire le minimum courant, comparé à chaque nouvel élément : cela fait exactement $n-1$ comparaisons pour $n$ éléments.

Borne inférieure ($n-1$ comparaisons sont nécessaires). Argument par un graphe de « tournoi » : chaque comparaison élimine un candidat possible au rang de minimum (le plus grand des deux comparés ne peut plus être le minimum). Pour identifier avec certitude le minimum parmi $n$ éléments, il faut « éliminer » les $n-1$ autres candidats, chacun nécessitant d'avoir perdu au moins une comparaison. Comme chaque comparaison n'élimine qu'un seul candidat (celui qui s'avère le plus grand des deux), il faut au moins $n-1$ comparaisons.

Conclusion : $n-1$ est à la fois suffisant et nécessaire — l'algorithme naïf de parcours linéaire est donc déjà optimal pour ce problème.

Démontrer que la hauteur minimale d'un arbre binaire à $n$ nœuds est $\Theta(\log n)$, en utilisant le fait qu'un arbre binaire de hauteur $h$ a au plus $2^{h+1}-1$ nœuds.

Borne sur le nombre de nœuds. Un arbre binaire de hauteur $h$ (la racine étant à hauteur $0$) a au plus $1+2+4+\cdots+2^h=2^{h+1}-1$ nœuds (un nœud à la racine, au plus $2$ au niveau suivant, etc., somme géométrique).

Inversion de l'inégalité. Si l'arbre a $n$ nœuds, alors nécessairement $n\leq2^{h+1}-1$, soit $2^{h+1}\geq n+1$. En prenant le logarithme en base $2$ :

Conclusion. La hauteur $h$ est donc minorée par $\log_2(n+1)-1=\Theta(\log n)$. Cette borne est atteinte exactement par un arbre parfaitement équilibré (chaque niveau totalement rempli, sauf éventuellement le dernier) — c'est précisément ce que garantissent les arbres AVL ou rouge-noir, justifiant que leurs opérations de base sont en $O(\log n)$ dans le pire cas. $\square$

Construire (par insertions successives) un tas-min à partir de la séquence $5, 3, 8, 1, 9$ (insertion une à une, dans cet ordre), et donner le tableau final.

On insère chaque élément en fin de tableau, puis on le fait « remonter » (percoler) tant qu'il est inférieur à son parent.

Insertion de 5 : tableau $[5]$.

Insertion de 3 : $[5,3]$. Le parent de l'indice $1$ est l'indice $0$ (valeur $5$). Comme $3<5$, on échange : $[3,5]$.

Insertion de 8 : $[3,5,8]$. Le parent de l'indice $2$ est l'indice $0$ (valeur $3$). Comme $8>3$, pas d'échange : $[3,5,8]$.

Insertion de 1 : $[3,5,8,1]$. Le parent de l'indice $3$ est l'indice $1$ (valeur $5$). Comme $1<5$, échange : $[3,1,8,5]$. Le parent de l'indice $1$ est maintenant l'indice $0$ (valeur $3$). Comme $1<3$, échange : $[1,3,8,5]$.

Insertion de 9 : $[1,3,8,5,9]$. Le parent de l'indice $4$ est l'indice $1$ (valeur $3$). Comme $9>3$, pas d'échange.

Tableau final : $[1,3,8,5,9]$, qui correspond bien à un tas-min valide (on vérifie : parent de l'indice $2$ = indice $0$ = $1\leq8$ ✓ ; parent de l'indice $3$ = indice $1$ = $3\leq5$ ✓ ; parent de l'indice $4$ = indice $1$ = $3\leq9$ ✓).

Vrai ou faux : le tri par tas (heapsort) a une complexité $O(n\log n)$ dans le pire cas, contrairement au tri rapide (quicksort) dont le pire cas est $O(n^2)$.

Vrai. Le tri par tas construit un tas en $O(n)$, puis extrait le minimum (ou maximum) $n$ fois, chaque extraction coûtant $O(\log n)$ — soit $O(n\log n)$ dans tous les cas, sans dépendre de la configuration initiale des données, contrairement au tri rapide qui peut se dégrader en $O(n^2)$ sur certaines entrées défavorables.

Expliquer pourquoi une table de hachage peut se dégrader à $O(n)$ pour la recherche dans le pire cas, et quelles stratégies permettent de limiter ce risque en pratique.

Origine du pire cas. Une table de hachage répartit les clés dans des cases via une fonction de hachage $h$. Si, pour une raison quelconque (mauvaise fonction de hachage, ou distribution adversariale des clés), un grand nombre de clés se retrouvent dans la même case, la structure de chaînage associée à cette case devient une simple liste, et la recherche d'un élément dans cette liste coûte $O(k)$ où $k$ est le nombre de clés en collision — dans le pire cas, $k=n$ (toutes les clés dans la même case), donnant $O(n)$.

Stratégies de limitation en pratique :
1. Bonne fonction de hachage : choisir $h$ de sorte que les clés réelles (pas seulement théoriques) se répartissent le plus uniformément possible sur les cases disponibles.
2. Hachage universel (aléatoire) : tirer aléatoirement la fonction de hachage parmi une famille de fonctions au démarrage du programme, rendant impossible pour un adversaire de construire à l'avance un ensemble de clés provoquant systématiquement des collisions massives (attaque par déni de service sur les tables de hachage).
3. Redimensionnement dynamique (rehachage) : quand le facteur de charge (nombre de clés / nombre de cases) dépasse un seuil, on agrandit la table et on réinsère toutes les clés, ce qui maintient les chaînes courtes en moyenne.
4. Structures hybrides : remplacer les listes de chaînage par des arbres équilibrés au-delà d'un certain seuil de collisions dans une case (stratégie utilisée par certaines implémentations modernes de tables de hachage), garantissant $O(\log k)$ même dans le pire cas d'une case surchargée.

Démontrer que, dans un tas-min représenté par un tableau de taille $n$ (indexation à partir de $0$), le nombre de feuilles est exactement $\lceil n/2\rceil$.

Caractérisation des feuilles. Un nœud d'indice $i$ (pour $i\in\{0,\dots,n-1\}$) est une feuille si et seulement s'il n'a pas d'enfant gauche, c'est-à-dire si l'indice de son enfant gauche, $2i+1$, dépasse ou égale $n$ :

Comptage des indices vérifiant cette condition. Comme $i$ est un entier, la condition $i\geq(n-1)/2$ équivaut à $i\geq\big\lceil(n-1)/2\big\rceil$. Les indices valides sont donc $i\in\Big\{\big\lceil(n-1)/2\big\rceil,\dots,n-1\Big\}$, soit un nombre d'éléments égal à :

(on vérifie directement sur des petits cas : $n=5$ donne les indices $i\geq2$, soit $i\in\{2,3,4\}$, donc $3=\lceil5/2\rceil$ feuilles ; $n=6$ donne $i\geq\lceil5/2\rceil=3$, soit $i\in\{3,4,5\}$, donc $3=\lceil6/2\rceil$ feuilles).

Conclusion : le nombre de feuilles d'un tas à $n$ nœuds est exactement $\big\lceil n/2\big\rceil$. $\square$ Ce résultat est notamment utilisé pour borner le coût de la construction d'un tas en $O(n)$ (et non $O(n\log n)$ comme on pourrait naïvement le penser), car la majorité des nœuds (environ la moitié) sont des feuilles ne nécessitant aucune percolation.