Arbres et tas

#Arbres et tasCopier le lien

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é.

#Arbres binairesCopier le lien

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

#PropriétésCopier le lien

• 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'arbreCopier le lien

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

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'arbresCopier le lien

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 PythonCopier le lien

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 binairesCopier le lien

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ésCopier le lien

• 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 principalesCopier le lien

• 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

#Exercice : Implémentation d'un tas binaire minCopier le lien

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

#InstructionsCopier le lien

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 codeCopier le lien

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)Copier le lien

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

#Files de prioritéCopier le lien

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'usageCopier le lien

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