Piles (Stacks)

Principe LIFO

Une pile (stack) est une structure de données abstraite fonctionnant selon le principe LIFO (Last In, First Out) : le dernier élément inséré est le premier retiré. Ce comportement est analogue à une pile d’assiettes, on ne peut accéder qu’à l’assiette du sommet.

Trois opérations fondamentales définissent une pile :

• push : ajouter un élément au sommet, $O(1)$
• pop : retirer l’élément au sommet, $O(1)$
• peek/top : consulter l’élément au sommet sans le retirer, $O(1)$

Opération :  push(3)  push(7)  push(1)  pop()  peek()
Pile :       [^3]      [3,7]    [3,7,1]  [3,7]  → 7

Implémentation sur tableau

L’implémentation la plus directe repose sur un buffer linéaire avec un indice top repérant le sommet. C’est la version la plus performante grâce à la contiguïté mémoire (cf. cours précédent).

struct stack {
    int *data;
    int top;
    int capacity;
};

struct stack *stack_new(int capacity) {
    struct stack *s = (struct stack*)malloc(sizeof(struct stack));
    s->data = (int*)malloc(sizeof(int) * capacity);
    s->top = -1;
    s->capacity = capacity;
    return s;
}

void push(struct stack *s, int value) {
    if (s->top == s->capacity - 1) return; // stack overflow
    s->data[++s->top] = value;
}

int pop(struct stack *s) {
    if (s->top == -1) return -1; // stack underflow
    return s->data[s->top--];
}

int peek(struct stack *s) {
    if (s->top == -1) return -1;
    return s->data[s->top];
}

Avantages :

• Localité cache parfaite : le sommet est toujours dans les dernières lignes accédées.
• Aucun overhead de pointeurs.
• Toutes les opérations en $O(1)$.

Inconvénient :

• Capacité fixe (sauf si on accepte la réallocation amortie comme std::vector).

Implémentation sur liste chaînée

On peut aussi implémenter une pile via une liste simplement chaînée, où le sommet correspond à la tête de la liste.

struct node {
    int data;
    struct node *next;
};

void push(struct node **top, int value) {
    struct node *n = (struct node*)malloc(sizeof(struct node));
    n->data = value;
    n->next = *top;
    *top = n;
}

int pop(struct node **top) {
    if (*top == NULL) return -1;
    struct node *tmp = *top;
    int val = tmp->data;
    *top = tmp->next;
    free(tmp);
    return val;
}

L’insertion et la suppression en tête restent en $O(1)$, mais on retrouve les inconvénients bien connus de la liste chaînée : overhead mémoire de 8 octets par nœud (pointeur next), fragmentation mémoire, et cache misses systématiques. En pratique, l’implémentation sur tableau est quasiment toujours préférable sauf contraintes très spécifiques.

Applications des piles

La pile est omniprésente en informatique :

• Pile d’appels (call stack) : chaque appel de fonction empile un stack frame contenant les variables locales, l’adresse de retour et les registres sauvegardés. Le return dépile ce frame. C’est la raison pour laquelle une récursion infinie provoque un stack overflow.
• Évaluation d’expressions : la notation polonaise inversée (RPN) s’évalue directement avec une pile. Pour 3 4 + 2 * : on empile 3, empile 4, dépile les deux pour calculer 7, empile 7, empile 2, dépile les deux pour calculer 14.
• Parsing et vérification de parenthèses : pour chaque ( ou { on empile, pour chaque ) ou } on dépile et vérifie la correspondance. Si la pile est vide à la fin, l’expression est bien formée.
• Parcours en profondeur (DFS) : la pile (explicite ou implicite via la récursion) est le mécanisme sous-jacent du DFS sur les graphes et arbres.
• Undo/Redo : chaque action est empilée ; Ctrl+Z dépile la dernière action.

Files (Queues)

Principe FIFO

Une file (queue) fonctionne selon le principe FIFO (First In, First Out) : le premier élément inséré est le premier retiré. C’est le modèle de la file d’attente classique.

Deux opérations fondamentales :

• enqueue : ajouter un élément en queue (tail), $O(1)$
• dequeue : retirer l’élément en tête (head), $O(1)$

Opération :  enq(A)  enq(B)  enq(C)  deq()  deq()
File :       [A]     [A,B]   [A,B,C] [B,C]  [C]
                                      → A    → B

Implémentation sur buffer circulaire

L’implémentation naturelle d’une file repose sur le buffer circulaire que nous avons vu dans le cours précédent. On réutilise les deux indices read (head) et write (tail) pour une gestion FIFO efficace :

struct queue {
    int *data;
    int head;
    int tail;
    int size;
    int capacity;
};

struct queue *queue_new(int capacity) {
    struct queue *q = (struct queue*)malloc(sizeof(struct queue));
    q->data = (int*)malloc(sizeof(int) * capacity);
    q->head = 0;
    q->tail = 0;
    q->size = 0;
    q->capacity = capacity;
    return q;
}

void enqueue(struct queue *q, int value) {
    if (q->size == q->capacity) return; // full
    q->data[q->tail] = value;
    q->tail = (q->tail + 1) & (q->capacity - 1); // capacité = 2^k
    q->size++;
}

int dequeue(struct queue *q) {
    if (q->size == 0) return -1; // empty
    int val = q->data[q->head];
    q->head = (q->head + 1) & (q->capacity - 1);
    q->size--;
    return val;
}

On retrouve l’astuce du masque binaire ($C = 2^k$) pour éviter le modulo. Le champ size permet de distinguer sans ambiguïté un buffer plein d’un buffer vide (cas où head == tail dans les deux situations).

Implémentation sur tableau linéaire naïve (et ses problèmes)

Une implémentation naïve avec un simple tableau et un dequeue qui décale tous les éléments est en $O(n)$ par retrait. C’est exactement le problème que le buffer circulaire résout. De même, une implémentation sur liste simplement chaînée (avec pointeur head et tail) fonctionne en $O(1)$ pour les deux opérations, mais souffre du surcoût mémoire et de la fragmentation déjà discutés.

Deque (Double-Ended Queue)

Un deque (prononcé “deck”) généralise la file en autorisant l’insertion et la suppression aux deux extrémités :

• push_front / push_back : $O(1)$
• pop_front / pop_back : $O(1)$

Un deque peut donc simuler à la fois une pile et une file. L’implémentation classique repose sur un buffer circulaire avec gestion bidirectionnelle des indices. En C++, std::deque utilise une approche par blocs de mémoire contigus (un tableau de pointeurs vers des chunks de taille fixe), ce qui offre un compromis entre l’accès indexé en $O(1)$ amorti et la flexibilité d’insertion aux deux bouts.

File de priorité (Priority Queue)

Une file de priorité ne respecte plus l’ordre d’insertion mais retourne toujours l’élément de plus haute priorité. Les opérations fondamentales sont :

• insert : ajouter un élément avec une priorité
• extract_min (ou extract_max) : retirer l’élément de priorité extrême

L’implémentation naïve avec une liste non triée donne insert en $O(1)$ mais extract en $O(n)$. Avec une liste triée, c’est l’inverse. La bonne implémentation repose sur le tas binaire (binary heap), que nous détaillons dans la section suivante.

Applications des files

• Ordonnancement de processus : les schedulers utilisent des files (round-robin, files multi-niveaux) pour organiser l’accès CPU.
• Parcours en largeur (BFS) : la file est le mécanisme fondamental du BFS. On enfile les voisins du nœud courant, puis on défile le prochain nœud à explorer.
• Buffers de communication : les files de messages inter-processus (pipes, sockets, MPMC) que nous avons vues en cours de C/Unix sont des files.
• Impression, I/O : les requêtes d’impression ou d’E/S sont placées dans une file d’attente.

Structures de données hiérarchiques

Arbre binaire : définitions

Un arbre binaire est une structure hiérarchique où chaque nœud possède au plus deux enfants : un fils gauche et un fils droit. La terminologie essentielle :

• Racine (root) : le nœud sans parent, point d’entrée unique.
• Feuille (leaf) : un nœud sans enfant.
• Profondeur d’un nœud : nombre d’arêtes depuis la racine jusqu’à ce nœud.
• Hauteur de l’arbre : profondeur maximale parmi toutes les feuilles.

         10
        /  \
       5    15
      / \     \
     3   7    20

Un arbre binaire complet a tous ses niveaux remplis sauf éventuellement le dernier, qui est rempli de gauche à droite. Un arbre binaire parfait a tous ses niveaux complètement remplis.

Pour un arbre binaire de hauteur $h$ :

• Nombre maximal de nœuds : $2^{h+1} - 1$
• Nombre de nœuds à un niveau $k$ : au plus $2^k$
• Hauteur minimale pour $n$ nœuds (arbre complet) : $h = \lfloor \log_2 n \rfloor$

struct tree_node {
    int data;
    struct tree_node *left;
    struct tree_node *right;
};

L’overhead mémoire est de deux pointeurs par nœud (16 octets en 64 bits), auquel s’ajoute la donnée. Pour stocker un entier (4 octets), on utilise donc 20 octets minimum par nœud (avant padding), soit un overhead d’environ $O(5n)$, comparable à la liste doublement chaînée.

Parcours d’arbres

Le parcours d’un arbre binaire se fait soit en profondeur (DFS), soit en largeur (BFS). Le DFS existe sous trois variantes, définies par le moment où le nœud courant est traité par rapport à ses sous-arbres :

Parcours en profondeur (DFS), utilise une pile (implicite via la récursion) :

// Préfixe (preorder) : Nœud → Gauche → Droite
void preorder(struct tree_node *n) {
    if (!n) return;
    process(n->data);     // traiter le nœud
    preorder(n->left);
    preorder(n->right);
}

// Infixe (inorder) : Gauche → Nœud → Droite
void inorder(struct tree_node *n) {
    if (!n) return;
    inorder(n->left);
    process(n->data);     // sur un BST : ordre trié
    inorder(n->right);
}

// Postfixe (postorder) : Gauche → Droite → Nœud
void postorder(struct tree_node *n) {
    if (!n) return;
    postorder(n->left);
    postorder(n->right);
    process(n->data);     // libération mémoire, éval. expressions
}

Le parcours infixe est particulièrement important : appliqué à un arbre binaire de recherche, il produit les éléments en ordre croissant.

Parcours en largeur (BFS), utilise une file :

void bfs(struct tree_node *root) {
    struct queue *q = queue_new(1024);
    enqueue(q, root);
    while (q->size > 0) {
        struct tree_node *n = dequeue(q);
        process(n->data);
        if (n->left)  enqueue(q, n->left);
        if (n->right) enqueue(q, n->right);
    }
}

Ce parcours visite les nœuds niveau par niveau, de gauche à droite. Il est fondamental pour trouver le chemin le plus court dans un graphe non pondéré.

Tous ces parcours ont une complexité de $O(n)$ en temps (chaque nœud est visité une seule fois).

Arbre binaire de recherche (BST)

Un arbre binaire de recherche (Binary Search Tree) est un arbre binaire satisfaisant la propriété d’ordre : pour tout nœud $N$ :

• Tous les nœuds du sous-arbre gauche ont une valeur $< N$
• Tous les nœuds du sous-arbre droit ont une valeur $> N$

         10
        /  \
       5    15
      / \   / \
     3   7 12  20

La recherche suit une dichotomie naturelle :

struct tree_node *search(struct tree_node *root, int key) {
    if (root == NULL || root->data == key)
        return root;
    if (key < root->data)
        return search(root->left, key);
    return search(root->right, key);
}

L’insertion suit la même logique pour trouver la position correcte :

struct tree_node *insert(struct tree_node *root, int key) {
    if (root == NULL) {
        struct tree_node *n = (struct tree_node*)malloc(sizeof(struct tree_node));
        n->data = key;
        n->left = n->right = NULL;
        return n;
    }
    if (key < root->data)
        root->left = insert(root->left, key);
    else if (key > root->data)
        root->right = insert(root->right, key);
    return root;
}

Complexités :

Le pire cas en $O(n)$ survient lorsque l’arbre dégénère en liste chaînée (insertions dans l’ordre croissant ou décroissant). Insérer les éléments $1, 2, 3, 4, 5$ dans un BST produit :

1
 \
  2
   \
    3
     \
      4
       \
        5

La hauteur est alors $h = n - 1$ au lieu de $\lfloor \log_2 n \rfloor$. C’est ce problème fondamental que les arbres auto-équilibrés résolvent.

Arbre AVL

Un arbre AVL (Adelson-Velsky et Landis, 1962) est un BST auto-équilibré. Pour chaque nœud, le facteur d’équilibre est défini comme : $\text{bf}(N) = h(\text{gauche}) - h(\text{droite})$

La propriété AVL impose : $|\text{bf}(N)| \leq 1$ pour tout nœud $N$.

Lorsqu’une insertion ou suppression viole cette contrainte (facteur d’équilibre de $\pm 2$), on effectue des rotations pour rétablir l’équilibre. Il existe quatre cas :

Rotation simple droite (cas LL), le déséquilibre est causé par une insertion dans le sous-arbre gauche du fils gauche :

      z                  y
     / \               /   \
    y   T4    →       x     z
   / \               / \   / \
  x   T3            T1 T2 T3 T4
 / \
T1  T2

Rotation simple gauche (cas RR), symétrique du cas LL.

Double rotation gauche-droite (cas LR), insertion dans le sous-arbre droit du fils gauche : on effectue d’abord une rotation gauche sur le fils gauche, puis une rotation droite sur le nœud déséquilibré.

Double rotation droite-gauche (cas RL), symétrique du cas LR.

struct avl_node {
    int data;
    struct avl_node *left;
    struct avl_node *right;
    int height;
};

int height(struct avl_node *n) {
    return n ? n->height : 0;
}

int balance_factor(struct avl_node *n) {
    return n ? height(n->left) - height(n->right) : 0;
}

struct avl_node *rotate_right(struct avl_node *z) {
    struct avl_node *y = z->left;
    struct avl_node *T3 = y->right;
    y->right = z;
    z->left = T3;
    z->height = 1 + (height(z->left) > height(z->right) ? height(z->left) : height(z->right));
    y->height = 1 + (height(y->left) > height(y->right) ? height(y->left) : height(y->right));
    return y;
}

struct avl_node *rotate_left(struct avl_node *z) {
    struct avl_node *y = z->right;
    struct avl_node *T2 = y->left;
    y->left = z;
    z->right = T2;
    z->height = 1 + (height(z->left) > height(z->right) ? height(z->left) : height(z->right));
    y->height = 1 + (height(y->left) > height(y->right) ? height(y->left) : height(y->right));
    return y;
}

Après chaque insertion, on remonte la branche et on vérifie le facteur d’équilibre de chaque ancêtre. Si $|\text{bf}| = 2$, on identifie le cas (LL, RR, LR ou RL) et on applique la rotation appropriée.

Résultat : toutes les opérations (recherche, insertion, suppression) sont garanties en $O(\log n)$ dans le pire cas. La hauteur d’un arbre AVL de $n$ nœuds est bornée par $h < 1.44 \log_2(n+2)$, ce qui est très proche de l’optimum $\log_2 n$.

Le coût est une complexité d’implémentation accrue et un overhead d’un entier height par nœud. Les arbres Red-Black constituent une alternative (utilisés par std::map en C++) avec des contraintes d’équilibrage moins strictes mais des performances amorties similaires.

Tas binaire (Binary Heap)

Un tas binaire (binary heap) est un arbre binaire complet satisfaisant la propriété de tas :

• Min-heap : chaque nœud est $\leq$ ses enfants → la racine contient le minimum
• Max-heap : chaque nœud est $\geq$ ses enfants → la racine contient le maximum

La propriété fondamentale du tas est qu’il peut être stocké dans un simple tableau sans aucun pointeur, grâce à la complétude de l’arbre. Pour un nœud à l’indice $i$ (indexation à partir de 0) :

• Parent : $\lfloor (i - 1) / 2 \rfloor$
• Fils gauche : $2i + 1$
• Fils droit : $2i + 2$

Arbre :          1
               /   \
              3     5
             / \   /
            7   4 8

Tableau :   [ 1 | 3 | 5 | 7 | 4 | 8 ]
Indices :     0   1   2   3   4   5

Cette représentation en tableau est un point crucial : aucun pointeur, localité cache maximale, zéro overhead mémoire. C’est ce qui rend le tas supérieur au BST pour l’implémentation d’une file de priorité.

Insertion (sift up) : on ajoute l’élément à la fin du tableau (prochain emplacement libre dans l’arbre complet), puis on le fait “remonter” en l’échangeant avec son parent tant que la propriété de tas est violée.

void sift_up(int *heap, int i) {
    while (i > 0) {
        int parent = (i - 1) / 2;
        if (heap[i] >= heap[parent]) break; // min-heap
        int tmp = heap[i];
        heap[i] = heap[parent];
        heap[parent] = tmp;
        i = parent;
    }
}

void heap_insert(int *heap, int *size, int value) {
    heap[*size] = value;
    sift_up(heap, *size);
    (*size)++;
}

Complexité : $O(\log n)$, au plus $h$ échanges, où $h = \lfloor \log_2 n \rfloor$.

Extraction du minimum (sift down) : on remplace la racine par le dernier élément, puis on le fait “descendre” en l’échangeant avec le plus petit de ses fils tant que la propriété est violée.

void sift_down(int *heap, int size, int i) {
    while (1) {
        int smallest = i;
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        if (left < size && heap[left] < heap[smallest])
            smallest = left;
        if (right < size && heap[right] < heap[smallest])
            smallest = right;
        if (smallest == i) break;
        int tmp = heap[i];
        heap[i] = heap[smallest];
        heap[smallest] = tmp;
        i = smallest;
    }
}

int heap_extract_min(int *heap, int *size) {
    int min = heap;
    heap = heap[--(*size)];
    sift_down(heap, *size, 0);
    return min;
}

Complexité : $O(\log n)$.

Construction d’un tas (heapify) : donné un tableau quelconque de $n$ éléments, on peut construire un tas en $O(n)$ (et non $O(n \log n)$) en appliquant sift_down à partir du dernier nœud non-feuille en remontant vers la racine.

void build_heap(int *arr, int n) {
    for (int i = n / 2 - 1; i >= 0; i--)
        sift_down(arr, n, i);
}

L’intuition est la suivante : les feuilles (la moitié des nœuds) n’ont pas besoin de sift_down. Les nœuds proches des feuilles descendent de très peu, tandis que seule la racine peut descendre de $\log n$. Le coût total est :

$\sum_{k=0}^{\lfloor \log n \rfloor} \left\lceil \frac{n}{2^{k+1}} \right\rceil \cdot O(k) = O\left(n \sum_{k=0}^{\infty} \frac{k}{2^k}\right) = O(n \cdot 2) = O(n)$

La série $\sum_{k=0}^{\infty} k / 2^k$ converge vers 2, d’où le résultat. C’est un résultat important et contre-intuitif.

Heap sort : on construit un max-heap en $O(n)$, puis on extrait successivement le maximum ($n$ extractions en $O(\log n)$ chacune), ce qui donne un tri en $O(n \log n)$ in-place et sans allocation supplémentaire.

B-Tree

Un B-Tree d’ordre $m$ est un arbre de recherche auto-équilibré conçu pour les systèmes de stockage à accès par blocs (disques, SSDs). Contrairement au BST qui stocke une clé par nœud, un nœud de B-Tree contient jusqu’à $m - 1$ clés et $m$ fils. Ce principe est directement lié à celui des unrolled linked lists : on regroupe plusieurs clés par nœud pour réduire les accès disque (ou cache misses).

Propriétés d’un B-Tree d’ordre $m$ :

• Chaque nœud interne contient entre $\lceil m/2 \rceil - 1$ et $m - 1$ clés.
• Chaque nœud interne (sauf la racine) a entre $\lceil m/2 \rceil$ et $m$ fils.
• Toutes les feuilles sont au même niveau, l’arbre est toujours parfaitement équilibré.
• Les clés dans chaque nœud sont triées.

B-Tree d'ordre 3 (chaque nœud contient 1 à 2 clés) :

              [10 | 20]
             /    |    \
        [3|7]  [12|15]  [25|30]

La hauteur d’un B-Tree contenant $n$ clés est : $h \leq \log_{\lceil m/2 \rceil} \frac{n+1}{2}$

Ce qui signifie que pour $m$ grand (typiquement 100-1000 dans les bases de données), l’arbre est extrêmement plat. Un B-Tree d’ordre 1000 contenant un milliard de clés n’a que 3 niveaux.

La variante B+Tree stocke toutes les données dans les feuilles (les nœuds internes ne contiennent que des clés de routage), et les feuilles sont chaînées entre elles. C’est la structure utilisée par la quasi-totalité des SGBD relationnels (PostgreSQL, MySQL/InnoDB) et des systèmes de fichiers (NTFS, ext4, Btrfs). Le chaînage des feuilles permet un parcours séquentiel efficace pour les requêtes de type WHERE x BETWEEN a AND b.

Le choix de l’ordre $m$ suit la même logique que le choix de $k$ pour les unrolled linked lists : on dimensionne le nœud pour qu’il tienne dans une page disque (typiquement 4 KB ou 8 KB) ou un multiple de la taille de ligne de cache, afin de minimiser les I/O.

Conclusion

Les structures abstraites (pile, file) sont des interfaces définies par leurs opérations, tandis que les structures concrètes (tableau, liste, tas, arbre) sont des implémentations. Le choix de l’implémentation dépend du profil d’accès et des contraintes matérielles.

L’arbre AVL garantit $O(\log n)$ strict au prix de rotations. Le tas binaire, stocké dans un tableau sans pointeur, est la structure optimale pour les files de priorité grâce à sa localité cache. Les B-Trees exploitent le même principe que les unrolled linked lists, regrouper les données par blocs, pour minimiser les accès I/O.

Le fil conducteur entre ces structures et celles du cours précédent reste le même : la localité mémoire et le ratio données/métadonnées sont souvent plus déterminants que la complexité asymptotique. Un tas binaire sur tableau (contiguïté parfaite, zéro pointeur) sera toujours plus rapide en pratique qu’un BST chaîné (fragmentation totale, 16 octets de pointeurs par nœud) malgré des complexités théoriques identiques.