Centrale Informatique MP 2000

Thème de l'épreuve Algorithmes de recherche dans les arbres bicoloriés rouges et noirs ; logique temporelle et expressions rationnelles
Principaux outils utilisés arbres binaires de recherche, implémentation en Caml et en Pascal, expressions rationnelles, automates finis, opérateurs logiques

Corrigé

(c'est payant, sauf le début): - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

Extrait gratuit du corrigé

(télécharger le PDF)
           

Énoncé complet

(télécharger le PDF)
                                         

Rapport du jury

(télécharger le PDF)
     

Énoncé obtenu par reconnaissance optique des caractères


INFORMA TIOUE Filière MP INFORMATIQUE Note :Toutes les réponses doivent être justifiées. Note :Vous indiquerez, au début de votre copie, si vous choisissez de rédiger vos programmes en PASCAL ou en CAML. Partie I - Algorithmique Dans cette artie on s'intéresse aux arbres bicolores ui sont une classe ? particulière des arbres binaires de recherche. I.A - Rappels et Notations I.A.1) Définitions Un arbre est un triplet fil : (SM, no, p) où : -- N est un ensemble fini dont les éléments sont appelés noeuds. -- n() est un élément particulier de 17\£ appelé racine. -- p est une fonction, nommée père, de 9\[ -- {no} dans 9\[ ayant la propriété suivante : Vn G N --{n0}, Elx & IN* | px(n) : n0 On rappelle que px dés1gne p o o p ; p0 dé51gne la fonction 1dent1té. x Un arbre vide est un arbre dégénère ayant un ensemble de noeuds vide (il n'a donc pas de racine). Dans ce qui suit, on considère un arbre non vide fll = (9\£, no, p) et les "a sont des éléments de N . ---- Si p(n1) : n2 ,on dit que n2 est le père de n1 , et que n1 est un fils de n2. -- Si px(n1) : n2 , on dit que n2 est un ascendant de n1 , et que n1 est un descen- dant de riz. -- Un chemin d'un noeud na à un noeud n b est une suite de noeuds (n1 = na,n2, ...,nk : nb) tel que Vie [l...k-- 1] , ni : p(ni+1) . --- Si Vn & Û\[ -- {no}, p(n) := n1 ,on dit que n1 est une feuille. Dans le cas contraire, on dit que n1 est un noeud interne. Concours Centrale-Supélec 2000 1/14 INFORMA TIQUE Filière MP Fil'ère MP -- Soit _'Î % = {(n e 9\[ --{n0})lp(n) : nl}. _'Î M est l'ensemble des fils de n1 . On appelle degré de n1 le cardinal de _7: 711 et degré maximal de l'arbre le plus grand des degrés des noeuds. -- Soit %... : {ne 9\£| 3xEUR lN,px(n)=nl}. Si p... est la restriction de 10 à 9\£ ... , alors <9\£ .... nl, p,,l> est un arbre, dit sous- arbre de fil de rac1ne n1 . -- La profondeur d'un noeud n est l'entier x 6 IN tel que px(n) : n0 . La hauteur d'un arbre est la profondeur maximale de ses noeuds. -- Un arbre ordonné est un arbre auquel on adjoint à chaque noeud un ordre to- tal sur ses fils. -- Un arbre n-aire est un arbre ordonné dont chaque noeud a exactement n fils (certains des fils pouvant être des arbres vides). -- Un arbre binaire est un arbre 2-aire. On nomme classiquement fils droit et fils gauche les deux fils de chaque noeud. Un arbre étiqueté est un quintuplet % : (9\£ , no, p, e, e) où : -- 9\£ , "o et p sont définis comme ci-dessus. -- e est un ensemble. -- e est une fonction de 9\[ dans a. Un arbre binaire étiqueté fil est noté }7l : (i, 54 g, /'Zld) . C'est l'arbre dont la ra- cine a pour étiquette ie 8, et pour sous-arbre gauche (respectivement sous-ar-- bre droit) ÿlg (respectivement flld). Un arbre binaire de recherche est un arbre binaire étiqueté, tel qu'il existe un ordre total sur e , et tel que si n est un noeud, flld et fll g ses sous-arbres droit et gauche (éventuellement des arbres vides) alors : ---- Vnge Âg,e(ng) Se(n) . -- Vnde fld, e(nd) Ze(n) . On suppose connu du candidat l'ordre de grandeur de la complexité de l'opéra-- tion de recherche d'un élément dans un arbre binaire de recherche ainsi que le principe d'insertion d'un élément dans un tel arbre. Concours Centrale-Supélec 2000 2/14 INFORMA TIQUE Filière MP I.A.2) Représentation -- Dans toute la partie algorithmique, on considère des arbres binaires étique- tés, et e est l'ensemble des entiers Z. -- Langage CAML : on n'utilisera pas ici la représentation classique d'un arbre sous forme de produit, car on souhaite pouvoir modifier un noeud sans en créer un nouveau. On utilisera donc un enregistrement. - Un arbre binaire étiqueté sera représenté ainsi : Type Noeud : mutable etiquette : int ; mutable gauche : ArbreBinaire ; mutable droit : ArbreBinaire ; andereBinaire : ArbreVide | Pointeur of Noeud ;; - Les fonctions suivantes seront utilisées : let est_vide : function ArbreVide "> true | _ --> false ;; let noeud = function ArbreVide ----> failwith "arbre vide" | Pointeur x --> X ;; - Voici un exemple d'utilisation de ces fonctions : la fonction échan- geant les fils gauche et droit d'un arbre sera écrite : let echange_gauche_droit a : if est_vide a then a else let temp : (noeud a) .gauche in (noeud a) .gauche <-- (noeud &) .droit; (noeud a) .droit <-- temp; a " Concours Centrale-Supélec 2000 3/14 INFORMATIQUE Filière MP -- Langage PASCAL - Un arbre binaire étiqueté sera représenté ainsi : TYPE ArbreBinaire = ANoeud ; Noeud = RECORD etiquette : INTEGER gauche, droit : ArbreBinaire END ; - La fonction suivante sera utilisée : FUNCTION est_vide (a : ArbreBinaire) :BOOLEAN ; BEGIN est_vide := (a : NIL); END; - Voici un exemple d'utilisation de cette fonction : la fonction échan- geant les fils gauche et droit d'un arbre sera écrite : F UNCTION echange_gauche_droit (a : ArbreBinaire) : Arbre-- Binaire ; VAR temp : ArbreBinaire ; BEGIN IF (est_vide (a)) THEN echange_gauche_droit := a ELSE BEGIN temp := aA.gauche; aA.gauche := a".droit; a".droit := temp; echange_gauche_droit := a END ; END ; I.B - Rotations Afin de pouvoir modifier la hauteur d'un arbre, on introduit, lorsqu'elles sont possibles, les opérations suivantes : Concours Centrale-Supélec 2000 4/14 INFOHMA TIQUE Filière MP I.B.l) Rotation gauche L'arbre obtenu en appliquant une rotation gauche à l'arbre (i,,flg1,(i2,flg2,ñd2)) est l'arbre (i2, (i,,ÿLgl,ÿlg2),ÿldz) . Rotation gauche a) Écrire la fonction rotation _gauche, recevant un ArbreBinaire comme seul ar-- gument, lui appliquant une rotation gauche, et retournant comme résultat l'ar-- bre modifié. On veillera à n'appliquer la rotation que si celle-ci est possible. Dans le cas contraire, l'arbre non modifié sera alors retourné. b) Montrer que si 54 est un arbre binaire de recherche, alors rotation _gauche (fl) est aussi un arbre binaire de recherche. I.B.2) Rotation droite La rotation droite appliquée à un arbre binaire est l'opération inverse de la ro- tation gauche. Ecrire la fonction rotation_droite, selon les mêmes principes que la fonction rotation_gauche. On fera un dessin au préalable. I.B.3) Doubles Rotations Soit 54 : (i,fllg,ÿld) un arbre binaire. La rotation gauche_droite de fil est l'arbre : rotation_droite (i , rotation _gauche (% g) , /'2ld) a) Écrire la fonction rotation gauche_droite. Là aussi, l'opération ne sera effec- tuée que si elle est possible. b) Dessiner le résultat obtenu après application de l'opération de rotation gau-- che-droite à l'arbre 5710 suivant : fix @ @ 9@ Concours Centrale-Supé/ec 2000 5/14 INFOHMA TIQUE Filière MP La rotation droite-gauche de 54 : (i,/q g,ÿld) est, s'il est défini, l'arbre : rotation _gauche (i , fl g , rotation_droite(f£læ) c) Écrire la fonction rotation_dmite_gauche. d) Dessiner le résultat obtenu après application de l'opération de rotation droi- te-gauche à l'arbre 20 défini en b). I.C - Arbres bicolores Un arbre bicolore est un arbre binaire de recherche dont les noeuds sont colorés d'une couleur parmi deux selon des règles particulières énoncées ci-dessous. Si le rouge et noir sont classiquement utilisés, nous prendrons ici le blanc et noir. On choisira d'autre part de ne pas étiqueter les feuilles. I.C.1) Nouvelle représentation On modifie la représentation des arbres afin d'ajouter l'information de coloriage. On en profite pour ajouter dans un noeud un champ indiquant le père qui sera un arbre vide dans le cas de la racine. Les feuilles, non étiquetées, et qui ont une couleur fixe (voir ci--dessous) seront systématiquement représentées par des ar-- bres VidéS. On supposera que les fonctions de rotation ont été corrigées pour te- nir compte de cette nouvelle représentation. -- En CAML, un arbre binaire bicolore sera représenté ainsi : type Couleur : Blanc | Noir ; ; type Noeud : mutable etiquette : int ; mutable couleur: Couleur; mutable gauche: ArbreBinaire ; mutable droit: ArbreBinaire; mutable pere : ArbreBinaire ; and ArbreBinaire : ArbreVide | Pointeur of Noeud '.. '. Concours Centrale-Supé/ec 2000 6/14 INFORMA TIQUE Filière MP - En PASCAL, un arbre bicolore sera représenté ainsi : TYPE TCouleur : (Blanc,Noir); ArbreBinaire : ANoeud; Noeud : RECORD etiquette : INTEGER ; couleur : TCouleur; gauche, droit, pere: ArbreBinaire END; Un arbre bicolore doit satisfaire aux contraintes suivantes (en plus d'être un ar- bre binaire de recherche) : (A-1) Un noeud est soit blanc, soit noir. (A-2) Une feuille est noire. (A-8) La racine est noire. (A-4) Le père d'un noeud blanc est noir. (A--5) Tous les chemins partant d'un noeud donné et se terminant à une feuille contiennent le même nombre de noeuds noirs (sans prendre en compte le noeud de départ) On nomme hauteur noire d'un noeud n appartenant à un arbre bicolore (on la note hn(n)) le nombre de noeuds noirs sur les chemins partant de ce noeud et aboutissant à une feuille (sans prendre en compte n ). Cette fonction est bien dé- finie grâce à (A-5). On nomme hauteur noire d'un arbre bicolore la hauteur noire de sa racine. 1.0.2) Hauteur d'un arbre bicolore a) Montrer qu'un sous-arbre de racine n d'un arbre bicolore contient au moins h . 2 "("'--1 noeuds 1nternes. b) Montrer qu'un arbre bicolore comportant l noeuds internes a une hauteur au plus égale à 210g2(l + 1) . 0) Que peut-on dire de l'ordre de grandeur de la complexité de la recherche d'un élément dans un arbre bicolore ? 1.0.3) Insertion dans un arbre bicolore Pour insérer un nouveau noeud n dans un arbre bicolore, on commence par l'in- sérer selon l'algorithme d'insertion dans un arbre binaire de recherche (on par-- lera d'insertion initiale), en lui affectant la couleur blanc. L'arbre obtenu ainsi n'est plus forcément bicolore, et il faut le modifier pour lui redonner cette pro- Concours Centrale-Supélec 2000 7/14 INFOHMA T/QUE Fil/ère MP priété. L'algorithme utilisé est itératif, donc si au départ, le noeud courant n a deux fils qui sont des arbres vides, cette propriété n'est plus obligatoirement res- pectée aux itérations suivantes. a) Dans le cas où l'arbre initial est vide, quelle modification faut--il apporter pour que l'arbre résultat soit de nouveau bicolore '? b) Dans le cas d'un arbre non vide, que peut-on dire de l'arbre résultat si le père de n après insertion initiale est noire ? On se place maintenant dans le cas où le père de n après insertion initiale (ou après itération) est blanc. Le père de 71 n'est donc pas la racine, et a lui-même un père qui est noir. Les différents cas possibles sont donc (on note fd et fg les deux fils de n , ;) son père, q son grand père, f son frère et 0 son oncle) : q = p p = p...) fg Cas n°1 d) À quelle condition simple l'arbre global obtenu est-il bicolore '? e) Que faut-il faire si la condition n'est pas vérifiée afin de retrouver un arbre bicolore '? f) Quelle transformation faut-il effectuer dans les cas n°2, 3 et 4 afin de retrou- ver un arbre bicolore, toujours en supposant que 0 est blanc ? On suppose maintenant que l'oncle o de n est noir. Dans le cas n°1, on effectue la transformation suivante : q = p fg fd Cas n°1 g) Quelle est cette transformation '? h) Montrer que l'arbre global obtenu est bicolore. i) Montrer que dans le cas n°2, si on effectue la même transformation, on ne peut pas trouver une coloration des noeuds p, q. 71 telle que les contraintes (A-4) et (A-5) soient vérifiées. j) Dessiner et nommer la transformation à effectuer dans le cas n°2 qui permet- te de conserver la hauteur noire vue du père du sous-arbre. k) Dessiner et nommer une transformation à effectuer dans le cas n°3. 1) Dessiner et nommer la transformation à effectuer dans le cas n°4. Concours Centrale-Supé/ec 2000 9/14 INFORMA TIOUE Filière MP On suppose écrite la fonction d'insertion dans un arbre binaire de recherche. Cette fonction retourne l'arbre binaire dont la racine est colorée en blanc et est étiquetée par l'élément qui vient d'être inséré. -- En CAML, la fonction a le profil suivant : inserer_arbre_binaire : ArbreBinaire --> int ----> ArbreBinaire :  - En PASCAL, la fonction est déclarée ainsi : FUNCTION inserer_arbre_binaire (& : ArbreBinaire; val : INTEGER) : ArbreBinaire; m) Ecrire une fonction inserer_arbre_bicolore, ayant le même profil que la fonction inserer_arbre_binaire, mais réalisant l'insertion dans un arbre bico-- lore. TS VP Concours Centrale-Supélec 2000 10/14 INFORMA TIOUE Filière MP Partie II - Logique et automates Quand on considère un système (pris au sens large du terme), la logique permet d'exprimer les propriétés des états du système. La logique temporelle permet d'exprimer l'évolution de l'état d'un système. Cette évolution est considérée comme une suite d'états. II.A - Définitions et notations On considère un ensemble non vide E : {el, ...,en} . Une propriété p des éléments de E est un sous ensemble de E . On dira que e e E vérifie la propriété p quand e e p . On notera V la propriété satisfaite par tous les éléments de E , c'est à dire celle qui correspond à l'ensemble E . On notera F la propriété satisfaite par aucun élément de E , c'est à dire celle qui correspond à l'ensemble @ . Soit ? : {p1,p2, ...,pk} un ensemble de propriétés de E . L'ensemble des formules de logique temporelle basées sur 'P est définie comme suit à partir des propriétés, avec les opérateurs booléens v, A ,--. (ou, et, non) et les opérateurs temporels 0 (juste après), [Il (désormais), <> (finalement), 3 (jusqu'à). Si p est une propriété, et si $ et w sont des formules de logique temporelle : ' P - ( A w) ' ( V W) ' (n) ' (O 'P) - (®5W) ' 0 ($) ' Û(d>) sont des formules de logique temporelle. Toute formule de logique temporelle est construite à partir des règles précéden- tes. Pour simplifier l'écriture des formules, on négligera les parenthèses quand il n'y a pas d'ambiguïté possible. Par exemple, on écrira @ /\ \|J au lieu de (© A in), et El (@ A w) au lieu de D(((b A m)) . On utilisera aussi le connecteur --> , q> --> w étant l'abréviation de (--. V W) si et seulement si (o,i) |= q; ou (o,i) |=\ll ; (R-3) (Gi) l= ( A W) si et seulement si (o,i)|= @ et (m') l=W ; (R-4) (G,i)l= (n'?) si et seulement si i< |6l et (o, i) ne satisfait pas (1) ; (R-5) (o,i)|= (Oo): si et seulement si (o,i+1)|= @ ; (R--6) (o,i)}= (ch) si et seulement si pour tout j tel que is j < |0| , (o,j)|= @) ; (R-7) (o,i)|= (N)) si et seulement s'il existe j tel que is j < lol et (o,j)|=@ ; (R-8) (o,i)|= (©8111) si et seulement s'il existe j tel que is j  D--up On dit que (1) a comme conséquence w , ce qu'on note @ => w si seulement si pour tout E , tout ensemble ? de propriétés sur E , toute suite 6 et tout i , si (o,i) }= (1) , alors (o,i) |=1u Exemple: Dd>=> <><1>. On dit que @ et w sont équivalentes si @) => 141 et w => (1) , on notera cela «) «=> w . Concours Centrale-Supélec 2000 12/14 INFORMA TIQUE Filière MP II.B - Satisfaction de formules II.B.l) Pour l'ensemble E : {e0,el,ez}, les propriétés p : {e0,e1} et q : {e0, e2} , et la suite 6 : (e1,e1,e1,e2,el,el,eo, eo) , les formules suivantes sont- elles satisfaites '? . (614)l= DP ° (6,2)I=O(Dq) ° (5,1)l=0(Dp) ' (0,1)l= p5q II.B.2) Soit p une propriété. Quelle sont les suites o vérifiant o|=El (Op) ? II.B.8) Donner une formule Dern telle que (o,i) |= Bern si et seulement si ci est le dernier élément de la suite, c'est-à-dire si i : lol -- 1 . Bern pourra être uti- lisée par la suite. II.B.4) Soit p une propriété. Donner, avec justification préalable, une formule Pair , dépendant de p , telle que o |= Pair si et seulement si la propriété p est vérifiée pour tous les éléments 52*i tel que 0 S 2*i < lol et seulement ceux-là. II.B.5) Les équivalences suivantes sont-elles satisfaites ? [] <> q> «=> <> D @ @ <> <> @ (Û) V (DW) <= Û(4>M(Dw)=> <>(QMEW) (°OE)A(ÜW)@Û (W)/"V) (©Sw)5w «=> d>8w Si oui le démontrer, si non donner un contre exemple. II.B.6) Montrer que l'opérateur <> peut s'exprimer à l'aide de l'opérateur S et de V, plus précisément, que pour toute formule (1) où apparaît <> , il existe une formule w équivalente où n'apparaît pas <> , mais où apparaissent S et V. II.B.7 ) Montrer que toute formule de logique temporelle est équivalente à une formule où n'apparaissent comme opérateurs temporels que 0 et S . II.C - Rappels de définitions et de notations sur les automates finis. Un automate fini non déterministe fil : (E,eo, F, A, 8) est défini ainsi : - E est l'ensemble (fini) des états ; - e() est un élément distingué de E appelé état initial ; - F est un sous ensemble de E appelé ensemble des états finals ; - A est l'alphabet d'entrée ; - 8 est une application de E >Opb)} L2 : {oeA*lol=Û(Pa-->Opb)l L3 = {55 A*IG |= <>(lîl(JDOE-->Opb))} ooo FIN 000 Concours Centrale--Supélec 2000 14/14

Extrait du corrigé obtenu par reconnaissance optique des caractères


 Centrale Informatique MP 2000 -- Corrigé Ce corrigé est proposé par Codrin Nichitiu (ENS Lyon) ; il a été relu par Lionel Eyraud (ENS Lyon) et Brice Goglin (ENS Lyon). L'épreuve porte d'une part sur des algorithmes de rotation et d'insertion dans des arbres binaires bicoloriés, et d'autre part, sur des notions introductives de logique temporelle, et leurs liaisons avec les automates finis et langages rationnels. La première partie demande la rédaction de fonctions de rotation dans des arbres binaires de recherche, pour bien fixer les notions. Après des modifications dans la structure de données, on continue avec une étude détaillée des différents cas possibles de déséquilibre lors de l'insertion dans un arbre bicolorié. À l'aide des dessins et questions, le squelette de l'algorithme d'insertion se dessine pas à pas, et le dernier exercice demande sa rédaction complète. La deuxième partie présente les opérateurs de base de la logique temporelle, à partir d'exemples d'abord simples, puis portant sur l'élaboration de quelques formules testant des propriétés des suites d'événements. La fin est plus délicate, faisant appel à l'intuition pour relier les opérateurs temporels à ceux des langages et expressions rationnelles, afin de trouver des équivalences entre les formules de logique et les automates finis, à travers quelques exemples. Indications I.C.2 Procéder par récurrence sur la hauteur (selon sa définition « classique ») ; la hauteur à utiliser est celle dont il est question juste après. I.C.3.d Penser aux autres sommets, à l'extérieur du sous-arbre dessiné. I.C.3.e La réponse est dans l'énoncé, juste avant la question I.C.3.a. I.C.3.h Vérifier les conditions une par une. I.C.3.j Penser à rééquilibrer une partie du sous-arbre dessiné pour ce cas, par une rotation. I.C.3.k Raisonnement symétrique. I.C.3.m Hiérarchiser l'étude des cas, les étudier séparément, pas à pas. Le tout est à mettre dans une boucle, après avoir inséré comme dans un arbre binaire le nouvel élément. L'algorithme s'arrête rapidement dans certains cas. II.B.3 Penser à V et aux opérateurs temporels bornés. II.B.4 Utiliser la formule Dern avec un opérateur temporel d'itérations de « boucle » (du type until, « jusqu'à » en français). Penser à prévoir tous les cas, mais à obliger la vérification de se poursuivre avec la bonne parité. II.B.5 Appliquer simplement les définitions pour les deux premières et la dernière identité. Pour les autres, chercher des contre-exemples très simples. II.C.1 Trouver les équivalences entre opérations de langage (étoile, concaténation, etc.) et opérateurs de logique temporelle : clairement l'étoile correspond à l'itération, et la concaténation au , avec l'opérateur (suivant). Partie I Algorithmique I.B.1.a En CAML, cela donne let rotation_gauche = function ArbreVide -> ArbreVide | arbre -> if est_vide (noeud arbre).droit then arbre else let ideux = (noeud arbre).droit in let agdeux = (noeud ideux).gauche in (noeud arbre).droit <- agdeux; (noeud ideux).gauche <- arbre;ideux;; et en Pascal, function rotation_gauche(a:ArbreBinaire):ArbreBinaire; var ideux,agdeux:ArbreBinaire; begin if(est_vide(a)) then rotation_gauche := a else if(est_vide(a^.droit)) then rotation_gauche := a else begin ideux := a^.droit; agdeux := ideux^.gauche; a^.droit := agdeux; ideux^.gauche := a; rotation_gauche := ideux; end; end; Il y a un parallélisme assez important entre le code CAML et le code Pascal. En effet, les champs mutable se comportent bien comme des variables : les let créent des copies, et les assignements changent complètement la valeur. Par contre, on s'affranchit de la notion « concrète » de pointeur, qui en Pascal fait qu'on doit tester l'égalité avec nil, tandis qu'en CAML il y a la variante « abstraite » du type arbre vide. I.B.1.b Le fils gauche de i2 contient des noeuds dont les étiquettes sont toutes plus grandes que e(i1 ) ; après la rotation, il respecte la définition de l'arbre binaire, en tant que fils droit de i1 , d'où e(i1 ) 6 e(i2 ) . Le fils droit de i2 contient des noeuds dont les étiquettes sont toutes plus grandes que e(i2 ) ; en tant que fils droit de i2 après la rotation, il respecte aussi la définition de l'arbre binaire. Enfin, les noeuds du fils gauche de i1 ont des étiquettes plus petites que e(i1 ), et après rotation ce sous-arbre reste fils gauche de i1 . En conclusion, toutes les relations définissant un arbre binaire de recherche sont respectées après la rotation. I.B.2 En CAML, cela donne let rotation_droite = function ArbreVide -> ArbreVide | arbre -> if est_vide (noeud arbre).gauche then arbre else let ideux = (noeud arbre).gauche in let addeux = (noeud ideux).droit in (noeud arbre).gauche <- addeux; (noeud ideux).droit <- arbre; ideux;; et en Pascal, function rotation_droite(a:ArbreBinaire):ArbreBinaire; var ideux,addeux:ArbreBinaire; begin if(est_vide(a)) then rotation_droite := a else if(est_vide(a^.gauche)) then rotation_droite := a else begin ideux := a^.gauche; addeux := ideux^.droit; a^.gauche := addeux; ideux^.droit := a; rotation_droite := ideux; end; end; i1 Ad1 i2 Ag2 i2 Ad2 Ag2 i1 Ad2 Ad1 I.B.3.a En CAML le code s'écrit let rotation_gauche_droite = function ArbreVide -> ArbreVide | arbre -> (noeud arbre).gauche <(rotation_gauche ((noeud arbre).gauche)); (rotation_droite arbre);;