La faute qui sépare au lieu d'unir

Trois unions suffisent, sur quatre éléments. Partons de p = [| 0; 1; 2; 3 |].

unir 0 1  -->  p = [| 1; 1; 2; 3 |]     (* correct par hasard : 0 est une racine *)
unir 2 3  -->  p = [| 1; 1; 3; 3 |]     (* correct par hasard *)
unir 0 2  -->  p = [| 2; 1; 3; 3 |]     (* la faute *)

La troisième ligne écrase p[0], qui pointait vers $1$. Résultat mesuré : trouver 0 rend $3$ et trouver 1 rend $1$. L'élément $1$ a été expulsé de sa classe — l'opération a séparé là où on lui demandait d'unir.

Pourquoi la faute ne se voit pas tout de suite. Les deux premières unions donnent le bon résultat, parce que $0$ et $2$ étaient encore leurs propres racines. La faute ne se manifeste qu'à partir du moment où l'on unit un élément qui n'est plus une racine — c'est-à-dire, sur un jeu de tests trop petit, jamais.

La leçon de spécification. Le contrat de unir porte sur des classes, pas sur des éléments. Un code qui écrit dans p[x] parle d'un élément ; il faut donc, avant toute écriture, remonter aux deux racines. C'est exactement la discipline du chapitre chap:discipline : le jeu de tests doit contenir un cas où l'argument n'est pas une racine.