Original bug ID: 1721
Reporter: administrator
Status: closed
Resolution: fixed
Priority: normal
Severity: minor
Category: ~DO NOT USE (was: OCaml general)

Bug description

Toutes mes excuses : mon bug report #1720 est parti avant que j'ai pu
finir de le taper. Je termine donc mes explications concernant le bug
de la fonction Set.remove.

La fonction en cause est ici la fonction merge :

======================================================================
(* Merge two trees l and r into one.
All elements of l must precede the elements of r.
Assumes | height l - height r | <= 2. *)

let rec merge t1 t2 = match (t1, t2) with
  | (Empty, t) | (t, Empty) -> t
  | (Node(l1, v1, r1, h1), Node(l2, v2, r2, h2)) ->
      bal l1 v1 (bal (merge r1 l2) v2 r2)

======================================================================

Comme le dit le commentaire elle suppose une différence de hauteur
d'au plus 2 entre t1 et t2 mais clairement dans l'appel récursif
(merge r1 l2) ce n'est pas toujours le cas (par exemple si h(l1)=2,
h(l2)=4, h(r1)=0 et h(r2)=2).

Deux solutions possibles (au moins) :

• utiliser "join" (quand il sera corrigé :-) au lieu de "bal" et ne
  plus faire d'hypothèses sur les hauteurs de t1 et t2

• écrire merge à l'aide de deux fonctions remove_min et remove_max de
  la façon suivante :

  ======================================================================
  let rec remove_min = function
  | Empty -> assert false
  | Node (Empty, x, r, _) -> x, r
  | Node (l, x, r, _) -> let m,l' = remove_min l in m, bal l' x r

  let rec remove_max = function
  | Empty -> assert false
  | Node (l, x, Empty, _) -> x, l
  | Node (l, x, r, _) -> let m,r' = remove_max r in m, bal l x r'

  let merge2 t1 t2 = match t1, t2 with
  | Empty, t | t, Empty -> t
  | (Node (_, _, , h1) as t1), (Node (, _, _, h2) as t2) ->
  if h1 >= h2 then
  let m,t'1 = remove_max t1 in bal t'1 m t2
  else
  let m,t'2 = remove_min t2 in bal t1 m t'2

  Notez que l'on se rapproche là de la manière traditionnelle d'écrire
  remove.

Cordialement,

Jean-Christophe