type couleur = R | B (* les feuilles sont implicitement noires *) type 'a arbre = Feuille | Noeud of couleur * 'a arbre * 'a * 'a arbre (* une fonction qui réorganise l'arbre: on "remonte" le conflit éventuel entre deux noeuds rouges *) let balance = function (B,Noeud(R,Noeud(R,a,x,b),y,c),z,d) -> Noeud(R,Noeud(B,a,x,b),y,Noeud(B,c,z,d)) | (B,Noeud(R,a,x,Noeud(R,b,y,c)),z,d) -> Noeud(R,Noeud(B,a,x,b),y,Noeud(B,c,z,d)) | (B,a,x,Noeud(R,Noeud(R,b,y,c),z,d)) -> Noeud(R,Noeud(B,a,x,b),y,Noeud(B,c,z,d)) | (B,a,x,Noeud(R,b,y,Noeud(R,c,z,d))) -> Noeud(R,Noeud(B,a,x,b),y,Noeud(B,c,z,d)) | (c,a,y,b) as t -> Noeud (c,a,y,b) let insert (x,s) = let rec ins_aux = (function Feuille -> Noeud(R,Feuille,x,Feuille) | Noeud(c,a,y,b) as t -> if (xy then balance (c,a,y,ins_aux b) else t) in (* on force la racine à être noire *) let Noeud(_,a,y,b) = ins_aux s in Noeud(B,a,y,b) ;;