%
% Arbres binaires ordonnes.
%
%    <btree T> ::= tree(key:T value:<value> <btree T> <btree T>)
%               |  leaf
%
declare

%% renvoie un arbre vide
fun {NewTree} leaf end

%% renvoie found(V) si l'entree (X,V) est dans l'arbre T, notfound sinon
fun {Lookup X T}
   case T
   of leaf then notfound
   [] tree(key:Y value:V T1 T2) andthen X==Y then found(V)
   [] tree(key:Y value:V T1 T2) andthen X<Y then {Lookup X T1}
   [] tree(key:Y value:V T1 T2) andthen X>Y then {Lookup X T2}
   end
end

%% renvoie l'arbre T dans lequel on a insere l'entree (X,V)
fun {Insert X V T}
   case T
   of leaf then tree(key:X value:V leaf leaf)
   [] tree(key:Y value:W T1 T2) andthen X==Y then
      tree(key:X value:V T1 T2)
   [] tree(key:Y value:W T1 T2) andthen X<Y then
      tree(key:Y value:W {Insert X V T1} T2)
   [] tree(key:Y value:W T1 T2) andthen X>Y then
      tree(key:Y value:W T1 {Insert X V T2})
   end
end

local
   %% enleve le plus petit element de T (si possible)
   fun {RemoveSmallest T}
      case T
      of leaf then none
      [] tree(key:X value:V T1 T2) then
	 case {RemoveSmallest T1}
	 of none then X#V#T2
	 [] Xp#Vp#Tp then Xp#Vp#tree(key:X value:V Tp T2)
	 end
      end
   end
in
   %% renvoie l'arbre T dont on a retire toute entree ayant X comme cle
   fun {Delete X T}
      case T
      of leaf then leaf
      [] tree(key:Y value:W T1 T2) andthen X==Y then
	 case {RemoveSmallest T2}
	 of none then T1
	 [] Yp#Wp#Tp then tree(key:Yp value:Wp T1 Tp)
	 end
      [] tree(key:Y value:W T1 T2) andthen X<Y then
	 tree(key:Y value:W {Delete X T1} T2)
      [] tree(key:Y value:W T1 T2) andthen X>Y then
	 tree(key:Y value:W T1 {Delete X T2})
      end
   end
end