Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

1 de 1 Algorithmique Les arbres Florent Hivert Mél : Florent.Hivert@lri.fr Page

1 de 1 Algorithmique Les arbres Florent Hivert Mél : Florent.Hivert@lri.fr Page personnelle : http://www.lri.fr/˜hivert 2 de 1 Algorithmes et structures de données La plupart des bons algorithmes fonctionnent grâce à une méthode astucieuse pour organiser les données. Nous allons étudier quatre grandes classes de structures de données : Les structures de données séquentielles (tableaux) ; Les structures de données linéaires (liste chaînées) ; Les arbres ; Les graphes. 3 de 1 Problème de la recherche On aimerai avoir une structure de donnée où l’insertion et la recherche sont eﬃcace. Pour les tableaux : insertion en O(n), recherche en O(log(n)) Pour les listes : insertion en O(1), recherche en O(n) 4 de 1 Représentations graphiques d’arbres binaires et vocabulaire 15 4 33 3 9 11 28 7 21 25 12 29 15 7 6 5 nœuds branches une branche gauche une branche droite valeurs Ici : arbre, nœuds, branches ; arbre binaire, branches gauches, branches droites ; valeurs (ou étiquettes) des nœuds. 4 de 1 Représentations graphiques d’arbres binaires et vocabulaire 15 4 33 3 9 11 28 7 21 25 12 29 15 7 6 5 nœuds branches une branche gauche une branche droite valeurs Ici : arbre, nœuds, branches ; arbre binaire, branches gauches, branches droites ; valeurs (ou étiquettes) des nœuds. 4 de 1 Représentations graphiques d’arbres binaires et vocabulaire 15 4 33 3 9 11 28 7 21 25 12 29 15 7 6 5 nœuds branches une branche gauche une branche droite valeurs Ici : arbre, nœuds, branches ; arbre binaire, branches gauches, branches droites ; valeurs (ou étiquettes) des nœuds. 5 de 1 Déﬁnition récursive 15 4 33 3 9 11 28 7 21 25 12 29 15 7 6 5 nœud-racine arbre vide sous-arbre gauche sous-arbre droit Ici : (nœud-)racine, sous-arbre gauche, sous-arbre droit ; l’arbre vide, notion récursive d’arbre binaire valué (ou étiqueté) ; notion récursive de sous-arbre. 5 de 1 Déﬁnition récursive 15 4 33 3 9 11 28 7 21 25 12 29 15 7 6 5 nœud-racine arbre vide sous-arbre gauche sous-arbre droit Ici : (nœud-)racine, sous-arbre gauche, sous-arbre droit ; l’arbre vide, notion récursive d’arbre binaire valué (ou étiqueté) ; notion récursive de sous-arbre. 5 de 1 Déﬁnition récursive 15 4 33 3 9 11 28 7 21 25 12 29 15 7 6 5 nœud-racine arbre vide sous-arbre gauche sous-arbre droit Ici : (nœud-)racine, sous-arbre gauche, sous-arbre droit ; l’arbre vide, notion récursive d’arbre binaire valué (ou étiqueté) ; notion récursive de sous-arbre. 6 de 1 Arbres binaires étendus a 15 v 4 e 33 c 3 - 9 d 11 e 28 s 7 - 21 f 25 e 12 u 29 i 15 l 7 l 6 e 5 s feuilles Ici : feuilles ; notion récursive d’arbre binaire étendu. 6 de 1 Arbres binaires étendus a 15 v 4 e 33 c 3 - 9 d 11 e 28 s 7 - 21 f 25 e 12 u 29 i 15 l 7 l 6 e 5 s feuilles Ici : feuilles ; notion récursive d’arbre binaire étendu. 7 de 1 Vocabulaire h a u t e u r taille Ici : structure d’arbre binaire ; dimensions : taille, hauteur ; équilibre ; chemin issu de la racine, longueur d’un chemin. 7 de 1 Vocabulaire h a u t e u r taille Ici : structure d’arbre binaire ; dimensions : taille, hauteur ; équilibre ; chemin issu de la racine, longueur d’un chemin. 7 de 1 Vocabulaire h a u t e u r taille Ici : structure d’arbre binaire ; dimensions : taille, hauteur ; équilibre ; chemin issu de la racine, longueur d’un chemin. 7 de 1 Vocabulaire h a u t e u r taille Ici : structure d’arbre binaire ; dimensions : taille, hauteur ; équilibre ; chemin issu de la racine, longueur d’un chemin. 8 de 1 Arbre binaire de recherche 3 4 6 7 9 11 12 15 22 25 28 29 30 31 33 48 croissance stricte Ici : arbre binaire de recherche (ou ordonné) ; parcours inﬁxe (ou symétrique) ; recherche, insertion, suppression. 8 de 1 Arbre binaire de recherche 3 4 6 7 9 11 12 15 22 25 28 29 30 31 33 48 croissance stricte Ici : arbre binaire de recherche (ou ordonné) ; parcours inﬁxe (ou symétrique) ; recherche, insertion, suppression. 8 de 1 Arbre binaire de recherche 3 4 6 7 9 11 12 15 22 25 28 29 30 31 33 48 croissance stricte Ici : arbre binaire de recherche (ou ordonné) ; parcours inﬁxe (ou symétrique) ; recherche, insertion, suppression. 9 de 1 Arbre Tournoi 6 5 21 25 12 15 11 48 3 7 9 28 15 7 4 29 c r o i s s a n c e l a r g e Ici : arbre tournoi ; minimum, insertion, suppression du minimum. 9 de 1 Arbre Tournoi 6 5 21 25 12 15 11 48 3 7 9 28 15 7 4 29 c r o i s s a n c e l a r g e Ici : arbre tournoi ; minimum, insertion, suppression du minimum. 10 de 1 Termes anglo-saxons binary tree ; node, branch, value, label, root, subtree, leaf ; size, height, distance ; balanced tree ; path from the root, length of a path ; inﬁx traversal ; valued binary tree, label(l)ed binary tree, extended binary tree, binary search tree, ordered binary tree, tournament tree. 11 de 1 Applications des arbres Classiﬁcations : par questionnaire binaire : nœud = question, feuille = réponse ; branche gauche étiquetée par FAUX, branche droite par VRAI. Recherche : par arbres binaires de recherche. Files de priorité : par arbres-tournoi : gestion des tampons avec priorité. 12 de 1 Spéciﬁcation formelle Déﬁnition (Type abstrait ABin) Opérations : Vide : {} →ABin Noeud : ABin × ABin →ABin EstVide : ABin →Booleen SAG, SAD : ABin →ABin Préconditions : SAD(t), SAG(t) déﬁni seulement si non EstVide(t) Axiomes : EstVide(Vide()) = VRAI EstVide(Noeud(g, d)) = FAUX SAG(Noeud(g, d)) = g SAD(Noeud(g, d)) = d Noeud(SAG(t), SAD(t)) = t si non EstVide(t). 13 de 1 Voici la liste de tous les arbres jusqu’à la taille 3 : 13 de 1 Voici la liste de tous les arbres jusqu’à la taille 3 : 14 de 1 Voici la liste de tous les arbres de taille 4 : 15 de 1 Liste de tous les arbres à n Nœuds Algorithme Entrée : un entier positif ou nul n Sortie : une liste d’arbres res <- listeVide() si n = 0 alors ajoute(res, arbreVide()) retourner res pour i de 0 à n-1 faire lg <- ALGO(i); ld <- ALGO(n-1-i) pour g dans lg faire pour d dans ld faire ajoute(res, Noeud(g,d)) retourner res 16 de 1 Nombre de Catalan Proposition Le nombre d’arbres binaires à n nœuds est appelé n-ième nombre de Catalan noté Cn. Les nombre de Catalan vériﬁent la récurrence : C0 = 1 Cn = n−1 X i=0 CiCn−1−i . On en déduit Cn = (2n)! n!(n + 1)! . Voici les premières valeurs : C0 = 1, C1 = 1, C2 = 2, C3 = 5, C4 = 14, C5 = 42, c6 = 132 . 17 de 1 taille et hauteur Déﬁnition On déﬁnit deux fonctions sur les arbres binaires : Le nombre de noeuds appelé Taille : Taille(Vide) = 0 Taille(Noeud(a0, a1)) = 1 + Taille(a0) + Taille(a1) Le nombre de noeuds du plus long chemin appelé Hauteur : Hauteur(Vide) = 0 Hauteur(Noeud(a0, a1)) = 1+max{Hauteur(a0), Hauteur(a1)} 18 de 1 Comparaison taille/hauteur Proposition Pour tout arbre binaire de taille n et de hauteur h : h ⩽n ⩽2h −1 . 19 de 1 Noeuds Retenir Un noeud est dit interne s’il a deux ﬁls non vide. Sinon il est dit externe. internes externes 20 de 1 Retenir Une branche relie un noeuds à l’un des deux sous-arbres. Une branche est soit la branche gauche soit la branche droite d’un nœud. Une branche est interne lorsqu’elle relie deux nœuds ; elle est externe dans le cas contraire. internes externes En conséquence de quoi : un nœud interne possède deux branches internes ; un nœud externe possède au moins une branche externe. 21 de 1 Nombre de branches Proposition Tout arbre binaire de n nœuds possède 2n branches. Plus précisément, lorsque n ⩾1, il possède n −1 branches internes et n + 1 branches externes. 22 de 1 Retenir Un chemin de longueur k issu de a est un couple de la forme : (a, ⟨b1, b2, . . . , bk⟩) pour lequel il existe t1, t2, . . . , tk tels que : en posant t0 = a, tj est le sous-arbre gauche ou droit de a′ j−1 selon que le bit de direction bj vaut 0 ou 1. On dit d’un tel chemin qu’il mène de a à tk. Le chemin de longueur nulle (a, ⟨⟩) mène de a à lui-même. uploads/Ingenierie_Lourd/ 06-arbres.pdf