type
	Typecle = integer;
	Arbre = ^Boite;
	Boite = record
			cle: Typecle;
			fg, fd: Arbre;
		end;

{-----------------------------------------coupe------------------------------------------------}

procedure coupe (c: Typecle; a: Arbre; var gauche, droit: Arbre);
{Coupe d'un arbre a suivant la cle c : deux arbres (abr) resultats sont obtenus,}
{gauche a toutes ses cles inferieures ou egales a c, et droit a toutes ses cles superieures a c}
	var
		lgauche, ldroit: Arbre;
begin
	if arbrevide(a) then
		begin
			gauche := nil;
			droit := nil
		end
	else
		begin
			if a^.cle <= c then
				begin
					gauche := a;
					coupe(c, a^.fd, lgauche, ldroit);
					gauche^.fd := lgauche;
					droit := ldroit;
				end
			else
				begin
					droit := a;
					coupe(c, a^.fg, lgauche, ldroit);
					droit^.fg := ldroit;
					gauche := lgauche;
				end;
		end;
end;