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)
                                         

É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);;