Chapitre 5 – Structures de Données: Piles, Files et Arbres

Les structures de données abstraites sont des modèles mathématiques fondamentaux en informatique qui définissent comment organiser et manipuler les données. Contrairement aux structures concrètes qui concernent l'implémentation physique en mémoire, les structures abstraites se concentrent sur l'interface et les opérations disponibles pour interagir avec les données.

Structure abstraite vs structure concrète : Une structure abstraite définit ce que vous pouvez faire avec les données (ajouter, supprimer, etc.), tandis qu'une structure concrète définit comment ces données sont stockées en mémoire (tableaux, listes chaînées, etc.).

1. La Pile (Stack)

Une pile est une structure de données qui suit le principe LIFO (Last In, First Out), ce qui signifie que le dernier élément ajouté est le premier à être retiré, comme une pile d'assiettes.

Opérations fondamentales

  • push(élément) : ajoute un élément au sommet de la pile
  • pop() : retire et renvoie l'élément au sommet de la pile
  • peek() or top() : renvoie l'élément au sommet sans le retirer
  • isEmpty() : vérifie si la pile est vide
Élément 3 Élément 2 Élément 1 pop() push()

Applications courantes

  • Gestion de l'historique de navigation (bouton retour des navigateurs)
  • Fonction "annuler" (CTRL+Z) dans les éditeurs
  • Évaluation d'expressions mathématiques
  • Vérification de la syntaxe (parenthèses équilibrées)
  • Algorithmes de parcours en profondeur (DFS)

Exemple d'implémentation en TypeScript

class Stack<T> {
private items: T[] = [];

push(element: T): void {
  this.items.push(element);
}

pop(): T | undefined {
  return this.items.pop();
}

peek(): T | undefined {
  return this.items[this.items.length - 1];
}

isEmpty(): boolean {
  return this.items.length === 0;
}

size(): number {
  return this.items.length;
}
}

// Exemple d'utilisation
const navigatorHistory = new Stack<string>();
navigatorHistory.push("page d'accueil");
navigatorHistory.push("page produits");
navigatorHistory.push("page contact");

// Simulation d'un bouton "retour"
console.log(navigatorHistory.pop()); // "page contact"

2. La File (Queue)

Une file est une structure de données suivant le principe FIFO (First In, First Out), où le premier élément ajouté est le premier à être retiré, comme une file d'attente dans la vie réelle.

Opérations fondamentales

  • enqueue(élément) : ajoute un élément à la fin de la file
  • dequeue() : retire et renvoie l'élément en tête de file
  • front() : renvoie l'élément en tête sans le retirer
  • isEmpty() : vérifie si la file est vide
Élément 3 Élément 2 Élément 1 dequeue() enqueue()

Applications courantes

  • Files d'attente pour les ressources partagées (imprimantes, processeurs)
  • Traitement des requêtes dans les serveurs web
  • Tampon (buffer) pour les flux de données
  • Algorithmes de parcours en largeur (BFS)
  • Planification de tâches

Exemple d'implémentation en TypeScript

class Queue<T> {
private items: T[] = [];

enqueue(element: T): void {
  this.items.push(element);
}

dequeue(): T | undefined {
  if (this.isEmpty()) return undefined;
  return this.items.shift();
}

front(): T | undefined {
  if (this.isEmpty()) return undefined;
  return this.items[0];
}

isEmpty(): boolean {
  return this.items.length === 0;
}

size(): number {
  return this.items.length;
}
}

// Exemple d'utilisation
const printQueue = new Queue<string>();
printQueue.enqueue("Document 1");
printQueue.enqueue("Document 2");
printQueue.enqueue("Document 3");

// Simulation d'impression
console.log(printQueue.dequeue()); // "Document 1"

3. L'Arbre Binaire

Un arbre est une structure hiérarchique non linéaire composée de nœuds connectés par des arêtes. Un arbre binaire est un type particulier d'arbre où chaque nœud possède au maximum deux enfants (gauche et droit).

Terminologie

  • Racine : le nœud supérieur, point d'entrée de l'arbre
  • Nœud parent : nœud qui a des enfants
  • Nœud enfant : nœud connecté à un nœud parent
  • Feuille : nœud sans enfants
  • Hauteur : longueur du plus long chemin de la racine à une feuille
  • Profondeur : distance d'un nœud à la racine
10 5 15 3 7 12 20 Racine Feuille Feuille

Types d'arbres binaires

  • Arbre binaire complet : tous les niveaux sont entièrement remplis, sauf peut-être le dernier niveau (rempli de gauche à droite)
  • Arbre binaire parfait : tous les niveaux sont entièrement remplis (2h-1 nœuds)
  • Arbre binaire de recherche (ABR) : pour chaque nœud, tous les éléments du sous-arbre gauche sont inférieurs au nœud, et tous les éléments du sous-arbre droit sont supérieurs
  • Arbre AVL : ABR équilibré où la différence de hauteur entre les sous-arbres gauche et droit de chaque nœud ne dépasse pas 1

Applications courantes

  • Systèmes de fichiers et répertoires
  • Base de données (index)
  • Compression de données (arbres de Huffman)
  • Évaluation d'expressions arithmétiques
  • Algorithmes de jeux (minimax)
  • Recherche rapide (ABR, AVL, etc.)

Exemple d'implémentation d'un arbre binaire de recherche en TypeScript

class TreeNode<T> {
value: T;
left: TreeNode<T> | null = null;
right: TreeNode<T> | null = null;

constructor(value: T) {
  this.value = value;
}
}

class BinarySearchTree<T> {
root: TreeNode<T> | null = null;

insert(value: T): void {
  const newNode = new TreeNode(value);
  
  if (this.root === null) {
    this.root = newNode;
    return;
  }
  
  const insertNode = (node: TreeNode<T>, newNode: TreeNode<T>): void => {
    if (newNode.value < node.value) {
      if (node.left === null) {
        node.left = newNode;
      } else {
        insertNode(node.left, newNode);
      }
    } else {
      if (node.right === null) {
        node.right = newNode;
      } else {
        insertNode(node.right, newNode);
      }
    }
  };
  
  insertNode(this.root, newNode);
}

search(value: T): boolean {
  const searchNode = (node: TreeNode<T> | null, value: T): boolean => {
    if (node === null) return false;
    if (node.value === value) return true;
    
    if (value < node.value) {
      return searchNode(node.left, value);
    } else {
      return searchNode(node.right, value);
    }
  };
  
  return searchNode(this.root, value);
}
}

// Exemple d'utilisation
const bst = new BinarySearchTree<number>();
bst.insert(10);
bst.insert(5);
bst.insert(15);
bst.insert(3);
bst.insert(7);

console.log(bst.search(7)); // true
console.log(bst.search(9)); // false

Comparaison des Performances

Structure Opération Complexité Moyenne Complexité Pire Cas
Pile push() O(1) O(1)
pop() O(1) O(1)
peek() O(1) O(1)
File enqueue() O(1) O(1)
dequeue() O(1) O(1)
front() O(1) O(1)
Arbre Binaire de Recherche insertion O(log n) O(n)
recherche O(log n) O(n)
suppression O(log n) O(n)

À Retenir

  • Pile (LIFO) : Parfaite pour les opérations d'annulation, l'analyse syntaxique, les parcours en profondeur (DFS). Chaque opération s'exécute en temps constant O(1).
  • File (FIFO) : Idéale pour la gestion de ressources partagées, le traitement séquentiel et les parcours en largeur (BFS). Offre également des performances en temps constant O(1).
  • Arbre Binaire : Structure polyvalente pour l'organisation hiérarchique des données. Les arbres binaires de recherche équilibrés comme l'AVL ou le Rouge-Noir garantissent des opérations en O(log n).
  • Le choix de la structure dépend du problème à résoudre : priorisez les piles pour les opérations séquentielles inversées, les files pour l'ordre chronologique, et les arbres pour les recherches optimisées.