La borne ${\log }_{2}n$ est atteinte

C'est le tournoi : on unit d'abord les éléments deux à deux, puis les paires deux à deux, et ainsi de suite.

(* Suite d'unions atteignant la hauteur maximale. Precondition : n = 2^k. *)
let tournoi u n =
  let pas = ref 1 in
  while !pas < n do
    let i = ref 0 in
    while !i < n do
      ignore (unir u !i (!i + !pas));
      i := !i + 2 * !pas
    done;
    pas := 2 * !pas
  done

Terminaison : pas double à chaque tour et la boucle s'arrête à $n$ ; il y a donc $k={\log }_{2}n$ tours. Invariant : après le tour de rang $j$, la forêt est faite de $n/2^j$ arbres de rang $j$ exactement, tous de même taille $2^j$.

Pourquoi la hauteur monte à chaque tour : au tour $j$, on unit deux arbres de même rang $j-1$, et c'est le seul cas où l'union par rang laisse la hauteur croître. Le tournoi force donc l'égalité à chaque étage.

Mesure sur la forêt réellement construite, sans aucune compression :

Et voilà pourquoi la compression n'est pas un luxe. La borne ${\log }_{2}n$ n'est pas pessimiste : elle est atteinte, par une suite d'unions parfaitement naturelle. Sans compression, un trouver coûte réellement ${\log }_{2}n$ sur cette entrée. C'est la compression qui, en aplatissant à l'usage, ramène le coût amorti à une constante.