Structures arborescentes : ======================================================================================== Il s'agit d'un type de donnée très répandu dont tout le monde à déjà une expérience dans la vie courante : ======================================================================================== - Arbre généalogique - Organigramme administratifs (hiérarchie dans l'armée, etc.). - Organisation d'un texte : Titre, chapitres, paragraphes, phrases - Manière d'organiser sa réflexion dans un jeu. - Etc. Mathématiquement un arbre est un graphe (un ensemble de sommets et d'arrêtes entre ces sommets) qui est connexe (de tout sommet on peut joindre un autre somment en suivant des arrêtes) et sans cycle (il n'existe pas de chemin partant d'un sommet et y retournant qui n'utilise pas deux fois une même arrête). Exemple d'arbre contenant des entiers (A) et vocabulaire : (A) 4 ** 4 est la racine de A / \ ** 4, 12, 5 sont des noeuds de l'arbre A / \ ** 12 et 5 sont respectivement fils gauche et droit de 4 dans A 12 5 / \ ** 5 est le sous-arbre droit de 4 (symétriquement sous arbre gauche) / \ / \ 18 25 / \ / 18 25 / / 9 / 9 ** 12 est une feuille car n'a ni sous-arbre gauche ni sous-arbre droit. ** A est un arbre binaire : chaque noeud a au plus deux sous-arbres (mais peut n'en avoir qu'un comme 25 par exemple). ** La profondeur d'un noeud est la distance à la racine, par convention la profondeur de la racine est 1. Donc la profondeur de 18 dans A est de 3. ** La hauteur d'un arbre est le maximum de la profondeur d'un noeud. A a pour profondeur 4. ** Un noeud interne de A est un noeud qui n'est pas une feuille. ======================================================================================== Les arbres vus comme un type inductif : ======================================================================================== Bien sûr en informatique on ne peut pas dessiner d'arbres. Ils sont implantés comme une structure de données particulières. On peut présenter les arbres comme des objets construits selon une définition inductive. Les arbres binaires d'entiers sont définis par : ** Base : l'arbre vide est un arbre binaire, qu'on peut noter "Vide" ** Induction : si A et B sont des arbres binaires et r est un entier alors le terme "Noeud(r,A,B)" désigne r / \ / \ A B c'est un arbre, qui est l'arbre de racine r, de sous-arbre gauche A et de sous-arbre droit B. En se basant sur cette définition on peut appliquer la méthode de réflexion vue dans le chapitre sur la récursivité. Les exemples les plus simples qui viennent à l'esprit sont les suivants: ** Calculer le nombre d'éléments dans un arbre : nb_elem nb_elem (Vide) = 0 nb_elem (Noeud(r,A,B)) = 1 + nb_elem(A) + nb_elem(B) ** Le calcul de la somme des entiers dans un arbre est similaire : sum_elem sum_elem (Vide) = 0 sum_elem (Noeud(r,A,B)) = r + sum_elem(A) + sum_elem(B) ** Le calcul de la hauteur d'un arbre est également direct : hauteur hauteur(Vide) = 0 hauteur(Noeud(r,A,B)) = 1 + max (hauteur(A),hauteur(B)) ** Prédicat sur la présence d'un élément dans un arbre : est_dans, essentiellement on remplace l'addition par le "ou" et le cas de base par faux (élément neutre du ou). est_dans(Vide,e) = faux est_dans(Noeud(x,A,B),e) = x=e ou est_dans(A,e) ou est_dans(B,e) ** Le calcul de la profondeur d'un noeud dans un arbre (on renvoit 0 si le noeud recherché n'est pas dans l'arbre) : la fonction prof est plus compliquée en effet, si l'élément recherché n'est pas à la racine il faut d'abord faire les appels récursifs à droite et à gauche. Si les deux appels récursifs retournent 0 alors l'élément n'est pas dans l'arbre et on retourne 0 sinon on prend le maximum des appels récursifs à gauche et à droite (car un des appels récursifs nous rendra un entier strictement positif) auquel il faut ajouter 1 (car on descend d'un cran dans l'arbre). prof (Vide,e) = 0 prof (Noeud(r,A,B),e) = si e=r alors 1 sinon soit pa=prof(e,A) et pb =prof(e,B) dans si pa=0 et pb=0 then 0 else 1+(max pa pb) On le voit c'est très similaire à ce qui se passe avec les listes, mais il faut faire, pour les récurrences les plus immédiates, deux appels récursifs : un sur le sous arbre gauche et un autre sur le sous arbre droit au lieu d'un seul sur les listes. La racine jouant le même rôle que le premier élément d'une liste. ======================================================================================== traitements infixe, suffixe et préfixe ======================================================================================== Il y a plusieurs manières de traiter les arbres de manière récursive systématique. Le manière la plus simple de le voir est de considérer les listes d'éléments qu'on peut associer à un arbre. Par exemple pour l'arbre (A) 4 / \ / \ 12 5 / \ / \ 18 25 / / 9 On peut le parcourir récursivement de trois manières différentes ** Préfixe : on sélectionne la racine, puis récursivement le sous-arbre gauche puis le sous-arbre droit. [4;12;5;18;25;9] ** Infixe : on traite les sous-arbre gauche puis la racine puis le sous-arbre droit. [12;4;18;5;9;25] ** Postfixe : on traite le sous-arbre gauche puis le droit puis la racine. [12;18;9;25;5;4] ==================================================================================== | | | ATTENTION : la séquence postfixe n'est pas la séquence préfixe écrite à l'envers ! | | | ==================================================================================== ======================================================================================== Application : évaluation d'un arbre représentant une expression arithmétique ======================================================================================== 12 + (18 * (9 - 7)) est la représentation séquentielle de cet arbre + / \ / \ 12 * / \ / \ 18 - / \ / \ 9 7 On peut évaluer la valeur de l'expression en effectuant un parcours postfixe de l'arbre. Les objets contenus dans les noeuds sont soit des valeurs (pour les feuilles de l'arbre) soit des oopérateurs. L'algorithme récursif revient à évaluer les sous arbres gauches et droits et appliquer l'opérateur en racine entre ses valeurs. Voir l'implantation dans le fichier contenant les fonctions caml. ================================================================================ Ordre Supérieur sur les arbres ================================================================================ Il est possible de définir des analogues des fonctions d'ordre supérieur map et fold vues sur les liste qui sont adaptées aux arbres. L'implantation, et l'utilistation de ces fonctions d'ordre supérieur est largement similaire à ce qui se passe sur les listes. - schéma map. - schéma de repliage. ================================================================================ Arbres binaires de recherche ================================================================================ Un arbre binaire de recherche a la propriété suivante (vraie pour tous les noeuds de l'arbre) : tout noeud du fils droit de la racine est plus petit que la racine, tout noeud du fils gauche de la racine est plus grand que la racine. Exemple d'arbre binaire de recherche su rles entiers. (* exemple de déclaration de type pour les abr su rles entiers*) type abr = Vide | Noeud of int*abr*abr;; (* Exemple d'arbre binaire de recherche 14 / \ / \ 12 25 / / \ / / \ 7 18 35 /\ / \ 28 47 *) let a1:abr = Noeud(14, Noeud(12,Noeud(7,Vide,Vide),Vide), Noeud(25, Noeud(18,Vide,Vide), Noeud(35, Noeud(28,Vide,Vide), Noeud(47,Vide,Vide) ) ) );; Opérations sur les arbres de recherche : -Savoir si e est dans A. let rec appartient (e:int) (a:abr) : bool = (* appartient e a <=> e est un noeud e l'arbre binaire de recherche a*) match a with Vide -> false | Noeud(r,fg,fd) -> if (e=r) then true else (if (e<=r) then (appartient e fg) else (appartient e fd));; Autre opérations : 1- Ajouter un élément dans abr ? 2- retirer un élément dans un abr ? 3- Trier en utilisant les abr (essentiellement un parcours infixe d'un abr). 1- Analyse de l'insertion d'un élément dans un ABR. Profile : insertion : un entier, un ABR -> un ABR Sémantique: insertion e A = l'arbre binaire de recherche A auquel on ajoute l'élément e. Equation de récurrence : insertion e Vide = Noeud(e,Vide,Vide) insertion e Noeud(r,fg,fd) = si (e<=r) alors Noeud(r,insertion e fg,fd) sinon Noeud(r,fg,insertion e fd) Implantation : let rec insertion (e:int) (a:abr) : abr = match a with Vide -> Noeud(e,Vide,Vide) | Noeud(r,fg,fd) -> if (e<=r) then Noeud(r,(insertion e fg),fd) else Noeud(r,fg,(insertion e fd));; 2- Suppression d'un élément dans un abr: Profile : suppression : un entier, un abr -> un abr Sémantique : suppression e a = l'arbre binaire de recherche a dans lequel on a supprimé une occurrence de e (s'il y en a sinon l'abr est inchangé). Algorithme : Trouver la place de l'élément à supprimer A partir de cette place trouver le plus petit élément du sous arbre droit qui remplace l'élément supprimé. Si ce plus petit élément avait un sous arbre droit le remonter d'un cran. let rec mise_a_jour (a:abr) : abr = match a with Noeud(r,fg,fd) -> if (fg=Vide) then (if (fd=Vide) then Vide else fd) else Noeud(r,(mise_a_jour fg),fd);; let rec plus_petit_element (a:abr) = match a with Noeud(r,fg,fd) -> if (fg=Vide) then r else (plus_petit_element fg);; let rec supprime_racine (a:abr) = match a with Noeud(r,Vide,Vide) -> Vide | Noeud(r,fg,fd) -> if (fd = Vide) then fg else (if (fg = Vide) then fd else let ppe=(plus_petit_element fd) and fdprime = (mise_a_jour fd) in Noeud(ppe,fg,fdprime)) ;; let rec suppression (e:int) (a:abr) : abr = match a with Vide -> Vide | Noeud(r,fg,fd) -> if (e=r) then (supprime_racine a) else (if (e résultat une liste triée. let rec parcours_infixe (a:abr) : int list = match a with Vide -> [] |Noeud(r,fg,fd) -> (parcours_infixe fg)@[r]@(parcours_infixe fd);; let rec abr_from_list (l:int list) : abr = match l with [] -> Vide | e::reste -> insertion e (abr_from_list reste);; let trier_abr (l:int list) : int list = parcours_infixe (abr_from_list l);;