Cours 7 - Arbres - IN305 PDF

Les Arbres Sandrine Vial [email protected] Novembre 2022 Les arbres Une des structures les plus importantes et les plus utilisées en informatique + / × ▶ Arbres gé...

Les Arbres Sandrine Vial [email protected] Novembre 2022 Les arbres Une des structures les plus importantes et les plus utilisées en informatique + / × ▶ Arbres généalogiques × − 2 a ▶ Arbres de classification ▶ Arbres d’expression 2 + a × a b 3 b Représentation de l’expression (2 × (a + b))/(a − 3 × b) + 2 × a Terminologie ▶ Un arbre : un ensemble de nœuds reliés entre eux par des arêtes. ▶ Trois propriétés pour les arbres enracinés : 1. Il existe un nœud particulier nommé racine. Tout nœud c autre que la racine est relié par une arête à un nœud p appelé père de c. 2. Un arbre est connexe. 3. Un arbre est sans cycle. Terminologie ▶ Un nœud peut avoir 0 ou plusieurs fils. ▶ Un nœud a exactement un père. La racine n1 n2 n3 n4 n5 n6 n7 Terminologie ▶ Un nœud peut avoir 0 ou plusieurs fils. ▶ Un nœud a exactement un père. La racine n1 n2 n3 n4 n5 n6 n7 Définition récursive ▶ Base : ▶ Un nœud unique n est un arbre ▶ n est la racine de cet arbre. ▶ Récurrence : ▶ Soit r un nouveau nœud ▶ T1 , T2 ,... , tk sont des arbres ayant pour racine r1 , r2 ,... , rk. ▶ Création d’un nouvel arbre ayant pour racine r et on ajoute une arête entre r et r1 r et r2 ,..., r et rk. Définition récursive : un exemple r r1 n2 n3 n4 r3 n5 n6 n7 r2 n8 n9 Propriétés d’un arbre Pour un arbre T a n sommets il y a équivalence entre les propriétés : ▶ T est un arbre ▶ T est connexe, et la suppression de toute arête le rend non connexe ▶ T est acyclique à n − 1 arêtes ▶ T est acyclique et l’ajout de toute arête le rend cyclique. Chemins, ancêtres, descendants,... ▶ Les ancêtres d un nœud : Nœuds trouvés sur le chemin unique entre ce nœud et la racine. ▶ Le nœud d est un descendant de a si et seulement si a est un ancêtre de d. ▶ Longueur d’un chemin = nombre d’arêtes parcourues. Généalogie ▶ La racine est un ancêtre de tous les nœuds. ▶ Chaque nœud est un descendant de la racine. ▶ Les nœuds ayant le même parent = enfants. ▶ Un nœud n et tous ses descendants = sous-arbre Feuilles et nœuds intérieurs ▶ Une feuille est un nœud qui n’a pas d’enfants ▶ Un nœud intérieur est un nœud qui a au moins 1 enfant. ▶ Tout nœud de l’arbre est : ▶ Soit une feuille ▶ Soit un nœud intérieur Mesures sur les arbres ▶ Taille de l’arbre T , notée taille(T) = nombre de nœuds. ▶ Nombre de feuilles noté nf(T). Hauteur ▶ La hauteur d’un nœud n, notée h(n), est la longueur du chemin depuis la racine jusqu’à n. ▶ La hauteur de l’arbre T , notée h(T ) : h(T ) = max h(x) x nœud de l’arbre Mesures ▶ Hauteur moyenne de l’arbre T , notée HM(T)= moyenne des hauteurs de tous les nœuds. LC (T ) HM(T ) = taille(T ) ▶ Hauteur moyenne externe de l’arbre T , notée HME(T) = moyenne des longueurs de tous les chemins issus de la racine et se terminant par une feuille. LCE (T ) HME (T ) = nf (T ) Les arbres binaires 1. Etude d’une classe particulière d’arbres 2. Propriétés 3. Algorithmes Les arbres binaires Tous les nœuds d’un arbre binaire ont 0, 1 ou 2 enfants. A B C D E F G H J K L M Les arbres binaires : Définitions ▶ Enfant gauche de n = racine du sous-arbre gauche de n. ▶ Enfant droit de n = racine du sous-arbre droit de n. ▶ Bord gauche de l’arbre = le chemin depuis la racine en ne suivant que des fils gauche. ▶ Bord droit de l’arbre = le chemin depuis la racine en ne suivant que des fils droits. Exemple : arbre binaire A B C D E F G H J K L M Exemple : arbre binaire A B C D E F G H J K L M Taille de l’arbre : Nombre de feuilles : Hauteur moyenne : Hauteur moyenne externe : Exemple : arbre binaire A B C D E F G H J K L M Taille de l’arbre : 12 Nombre de feuilles :6 Hauteur moyenne : 2.33 Hauteur moyenne externe : 3 Quelques arbres binaires particuliers 1. Arbre binaire filiforme 2. Arbre binaire complet ▶ 1 nœud à la hauteur 0 ▶ 2 nœuds à la hauteur 1 ▶ 4 nœuds à la hauteur 2 ▶... ▶ 2h nœuds à la hauteur h. ▶ Nombre total de nœuds d’un arbre de hauteur h : 20 + 21 + 22 + · · · + 2h = 2h+1 − 1 Quelques arbres binaires particuliers 1. Arbre binaire parfait : ▶ Tous les niveaux sont remplis sauf le dernier. ▶ Les feuilles sont le plus à gauche possible. 2. Arbre binaire localement complet : chaque nœud a 0 ou 2 fils. Propriétés sur les arbres (1) Lemme h(T ) ≤ taille(T ) − 1 Idée de Preuve Egalité obtenue pour un arbre filiforme. Propriétés sur les arbres (2) Lemme Pour tout arbre binaire T de taille n et de hauteur h on a : ⌊log2 n⌋ ≤ h ≤ n − 1 Idée de Preuve ▶ Arbre filiforme : arbre de hauteur h ayant le plus petit nombre de nœuds : n = h + 1 (seconde inégalité). ▶ Arbre complet : arbre de hauteur h ayant le plus grand nombre de nœuds : n = 2h+1 − 1 (première inégalité). Propriétés sur les arbres Corollaire Tout arbre binaire non vide T ayant f feuilles a une hauteur h(T ) supérieure ou égale à ⌈log2 f ⌉. Lemme Un arbre binaire localement complet ayant n nœuds internes a (n + 1) feuilles. Exploration ▶ Pas aussi simple que dans le cas des listes. ▶ Pas d’ordre naturel. ▶ Deux types de parcours : ▶ En largeur d’abord ▶ En profondeur d’abord Parcours en largeur d’abord + / × × − 2 a 2 + a × a b 3 b Ordre d’évaluation des nœuds : +/ × × − 2 a 2 + a × a b 3 b Type de données Mise en œuvre chaînée Enregistrement Nœud { Val : entier; Gauche : ↑ Nœud; Droit : ↑ Nœud; } Parcours en largeur d’abord Algorithme 1 Parcours en largeur d’un arbre binaire ParcoursEnLargeur(r : Nœud) ▷ Entrée : r (la racine d’un arbre) ▷ Sortie : traitement de tous les nœuds de l’arbre enraciné en r ▷ Variables locales : ce_niveau, niveau_inférieur : File ; o : Nœud ; Debut ce_niveau ← { r } ; tant que (ce_niveau est non vide) faire niveau_inférieur = { } ; pour chaque nœud o de ce_niveau faire traiter o ; niveau_inferieur ← niveau_inférieur ∪ enfants de o. fin pour ce_niveau ← niveau_inférieur ; fin tant que Fin Parcours en profondeur d’abord + / × × − 2 a 2 + a × a b 3 b Ordre d’évaluation des nœuds : ça dépend....  Visite de chaque noeud on traite le noeud la dernière fois qu'on le croise on traite le noeud la préfixe postfixe première fois qu'on le croise A B C infixe on traite le noeud la 2e fois qu'on le croise Parcours en profondeur d’abord + / × × − 2 a 2 + a × a b 3 b Parcours en profondeur d’abord + / × × − 2 a 2 + a × a b 3 b Parcours préfixe : +/ × 2 + a b − a × 3 b × 2 a Parcours en profondeur d’abord + / × × − 2 a 2 + a × a b 3 b Parcours infixe : 2 × a + b/a − 3 × b + 2 × a Parcours en profondeur d’abord + / × × − 2 a 2 + a × a b 3 b Parcours postfixe 2 a b + ×a 3 b × −/2 a × + Parcours en profondeur d’abord Algorithme 2 Parcours prefixe en profondeur d’un arbre binaire ParcoursEnProfondeur(r : Nœud) ▷ Entrée : r (la racine d’un arbre) ▷ Sortie : traitement de tous les nœuds de l’arbre enraciné en r Debut si r = ∅ traitement de l’arbre vide sinon traitement_prefixe(r) ; ParcoursEnProfondeur(r.Gauche) ; ParcoursEnProfondeur(r.Droit) ; fin si Fin Parcours en profondeur d’abord Algorithme 3 Parcours infixe en profondeur d’un arbre binaire ParcoursEnProfondeur(r : Nœud) ▷ Entrée : r (la racine d’un arbre) ▷ Sortie : traitement de tous les nœuds de l’arbre enraciné en r Debut si r = ∅ traitement de l’arbre vide sinon ParcoursEnProfondeur(r.Gauche) ; traitement_infixe(r) ; ParcoursEnProfondeur(r.Droit) ; fin si Fin Parcours en profondeur d’abord Algorithme 4 Parcours postfixe en profondeur d’un arbre binaire ParcoursEnProfondeur(r : Nœud) ▷ Entrée : r (la racine d’un arbre) ▷ Sortie : traitement de tous les nœuds de l’arbre enraciné en r Debut si r = ∅ traitement de l’arbre vide sinon ParcoursEnProfondeur(r.Gauche) ; ParcoursEnProfondeur(r.Droit) ; traitement_postfixe(r) ; fin si Fin