Aller au contenu principal

Arbres et tas

Progression

#Arbres et tas

Les arbres sont des structures de données hiérarchiques composées de nœuds connectés par des arêtes. Les tas sont une spécialisation des arbres binaires utilisés pour implémenter efficacement les files de priorité.

#Pourquoi des arbres ?

Les arbres permettent des recherches, insertions et suppressions en O(log n) quand ils sont équilibrés. Les arbres de recherche binaires (BST) maintiennent l’ordre; les variantes équilibrées (AVL, rouge‑noir) garantissent la hauteur logarithmique. On les choisit pour des ensembles/dictionnaires ordonnés et des parcours triés.

#Arbres binaires

Un arbre binaire est un arbre où chaque nœud a au plus deux enfants, appelés fils gauche et fils droit.

#Propriétés

  • Racine : Nœud initial de l'arbre
  • Feuille : Nœud sans enfants
  • Profondeur : Nombre d'arêtes de la racine à un nœud
  • Hauteur : Profondeur maximale des feuilles

#Représentation de l'arbre

Voici une représentation statique de l'arbre binaire construit par insertions successives :

bg-[rgba(var(--code-inline-bg),0.5)] text-[rgb(var(--fg))] px-1 roundedbg-[rgba(var(--code-inline-bg),0.5)] text-[rgb(var(--fg))] px-1 rounded
1       502      /  \3     30   704    / \5   20  40

Ce diagramme montre l'arbre final après l'insertion des valeurs 50, 30, 20, 40 et 70 selon les règles d'insertion d'un arbre binaire de recherche.

#Parcours d'arbres

  1. Parcours en profondeur (DFS) :

    • Préfixe (racine, gauche, droite)
    • Infixe (gauche, racine, droite)
    • Postfixe (gauche, droite, racine)

  2. Parcours en largeur (BFS) :

    • Niveau par niveau, de gauche à droite

#Implémentation en Python

pythonpython
1class Noeud:2    def __init__(self, valeur):3        self.valeur = valeur4        self.gauche = None5        self.droit = None6 7class ArbreBinaire:8    def __init__(self):9        self.racine = None10    11    def inserer(self, valeur):12        if self.racine is None:13            self.racine = Noeud(valeur)14        else:

#Tas binaires

Un tas binaire est un arbre binaire complet qui satisfait la propriété de tas :

  • Tas max : Chaque nœud est plus grand ou égal à ses enfants
  • Tas min : Chaque nœud est plus petit ou égal à ses enfants

#Propriétés

  • Arbre complet : Tous les niveaux sont remplis sauf éventuellement le dernier
  • Hauteur : O(log n) pour n éléments
  • Représentation : Souvent implémenté avec un tableau

#Opérations principales

  • Insérer : Ajouter un élément et maintenir la propriété de tas
  • Extraire le min/max : Retirer l'élément racine et réorganiser
  • Construire : Créer un tas à partir d'un ensemble d'éléments

#Animation: insertion dans un tas min

Append
Insérer en fin de tableau (dernier niveau)
Heapify up
Tant que parent > élément : swap
Arrêt
À la racine ou parent ≤ élément
Représentation en tableau

Pour un tas stocké dans un tableau indexé à partir de 0: parent(i)=(i-1)//2, gauche(i)=2i+1, droit(i)=2i+2. Cette représentation compacte exploite la complétude de l’arbre.

#Complexités (rappel)

  • BST équilibré: recherche/insert/supprimer O(log n); parcours trié en O(n).
  • Tas: insert O(log n), extraire min/max O(log n), peek O(1), construire un tas en O(n) par heapify.

#Exercice : Implémentation d'un tas binaire min

Implémentez un tas binaire min complet avec toutes les opérations nécessaires.

#Instructions

  1. Créez une classe TasBinaireMin qui implémente un tas min.
  2. Implémentez les méthodes :
    • inserer(element) : Ajouter un élément
    • extraire_min() : Retirer et retourner l'élément minimum
    • monter(i) : Remonter un élément pour maintenir la propriété de tas
    • descendre(i) : Faire descendre un élément pour maintenir la propriété de tas
  3. Utilisez un tableau pour représenter le tas.

#Exemple de code

pythonpython
1class TasBinaireMin:2    def __init__(self):3        self.elements = []4    5    def _parent(self, i):6        return (i - 1) // 27    8    def _gauche(self, i):9        return 2 * i + 110    11    def _droit(self, i):12        return 2 * i + 213    14    def _echanger(self, i, j):

#Arbres équilibrés (aperçu)

Les arbres équilibrés maintiennent une hauteur logarithmique pour garantir des opérations efficaces :

  • AVL : Différence de hauteur entre sous-arbres ≤ 1
  • Rouge-Noir : Propriétés de coloration pour maintenir l'équilibre
  • B-arbres : Nœuds avec plusieurs clés, utilisé dans les systèmes de fichiers

#Animation: opérations d’un tas binaire (min-heap)

Insert
Ajouter en fin puis monter (heapify up)
Extract‑min
Échanger racine ↔ dernier; descendre (heapify down)
Build‑heap
Heapify en O(n) à partir d’un tableau

#Files de priorité

Une file de priorité est une abstraction où chaque élément a une priorité :

  • Insertion : Ajouter un élément avec sa priorité
  • Extraire : Retirer l'élément de priorité maximale/minimale
  • Implémentation : Souvent avec un tas binaire

#Cas d'usage

  • Ordonnancement : Processus avec priorités dans les OS
  • Algorithmes : Dijkstra, Prim, Huffman
  • Simulation : Événements chronologiques