Probleme – Unir \& trouver avec annulation

1. La compression détruit ce qu'il faudrait remettre. Reprenons la forêt de l'exercice « Union par rang : dérouler », obtenue par sept unions en tournoi sur huit éléments :

parent = [| 0; 0; 0; 2; 0; 4; 4; 6 |]   rang = [| 3; 0; 1; 0; 2; 0; 1; 0 |]

Un trouver(7) avec compression modifie deux cases — $7$ et $6$ pointent désormais sur $0$ — sans qu'aucun historique d'unions n'en garde trace. Si l'on annule ensuite la dernière union, celle de $0$ et $4$, on obtient (mesuré) :

parent = [| 0; 0; 0; 2; 4; 4; 0; 0 |]   classes = 2

Le compteur annonce $2$ classes, et il y en a bien deux — mais ce ne sont pas les bonnes : $6$ et $7$ ont atterri dans la classe de $0$ alors qu'ils appartiennent à celle de $4$. La structure est corrompue en silence, et le compteur, lui, reste juste : le contrôle le plus naturel ne voit rien.

2. La variante avec historique. On renonce à la compression, et l'on empile ce qu'il faut pour revenir.

(* Unir & trouver avec annulation. Union par rang, SANS compression.
   hist retient, pour chaque union effective : (fils accroche, nouveau pere,
   le rang du pere a-t-il augmente ?). *)
type ufa = { p : int array; r : int array;
             mutable classes : int;
             mutable hist : (int * int * bool) list }

let creer n = { p = Array.init n (fun i -> i); r = Array.make n 0;
                classes = n; hist = [] }

(* Racine de x. PAS de compression : on ne modifie rien. Cout : O(log n). *)
let rec trouver u x = if u.p.(x) = x then x else trouver u u.p.(x)

let unir u x y =
  let a = trouver u x and b = trouver u y in
  if a = b then false
  else begin
    let a, b = if u.r.(a) < u.r.(b) then (b, a) else (a, b) in
    let monte = (u.r.(a) = u.r.(b)) in
    u.p.(b) <- a;
    if monte then u.r.(a) <- u.r.(a) + 1;
    u.classes <- u.classes - 1;
    u.hist <- (b, a, monte) :: u.hist;
    true
  end

(* Defait la derniere union effective. Precondition : hist non vide. *)
let annuler u = match u.hist with
  | [] -> failwith "rien a annuler"
  | (b, a, monte) :: reste ->
      u.p.(b) <- b;                                  (* b redevient racine *)
      if monte then u.r.(a) <- u.r.(a) - 1;
      u.classes <- u.classes + 1;
      u.hist <- reste

Correction de annuler : une union effective ne modifie que deux cases — p.(b) et, conditionnellement, r.(a) — et l'historique retient exactement ces deux informations. Comme aucune autre opération n'écrit dans les tableaux (c'est tout l'intérêt d'avoir supprimé la compression), remettre ces deux cases rétablit l'état antérieur, à l'identique.

Vérification, sur cinq éléments : après unir(0,1), unir(2,3) et unir(1,3), puis trois annuler, on retrouve exactement l'état de départ.

depart      : p = [|0;1;2;3;4|]  r = [|0;0;0;0;0|]  classes = 5
2 unions    : p = [|0;0;2;2;4|]  r = [|1;0;1;0;0|]  classes = 3
3e union    : p = [|0;0;0;2;4|]  r = [|2;0;1;0;0|]  classes = 2
tout defait : p = [|0;1;2;3;4|]  r = [|0;0;0;0;0|]  classes = 5   <-- identique

Complexité : annuler est en $O(1)$ ; trouver et unir sont en $O(\log n)$ au pire, par la proposition du chapitre — et cette borne, elle, ne dépendait pas de la compression.

3. L'arbitrage. On perd le coût amorti quasi constant : on passe de $O(\alpha (n))$ à $O(\log n)$, mesuré plus haut à $2,27$ sauts par opération contre $1,24$. On gagne la possibilité de revenir en arrière en $O(1)$, sans recopier la structure — ce qui, dans un parcours d'arbre de recherche à $2^n$ nœuds, est la différence entre praticable et impossible.

Et c'est un cas d'école du chapitre chap:abstraction : la même signature, deux réalisations, deux profils de coût. L'appelant choisit selon qu'il a besoin ou non de défaire.