Union par rang : dérouler

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

La hauteur vaut $3$, et les profondeurs sont [| 0; 1; 1; 2; 1; 2; 2; 3 |] : un seul élément est à profondeur $3$.

Comment on l'obtient sans exécuter. Les quatre premières unions apparient des rangs $0$ : elles créent quatre arbres de rang $1$. Les deux suivantes apparient des rangs $1$ : deux arbres de rang $2$. La dernière apparie deux rangs $2$ : un arbre de rang $3$. Le rang ne monte que sur une égalité, et c'est ici qu'il monte à chaque étage — c'est un tournoi à élimination directe.

Ce que le tableau des rangs dit. rang[0] = 3 : la racine. rang[4] = 2 et rang[2] = 1 : ce sont d'anciennes racines, dont le rang n'a plus de sens depuis qu'elles ont été accrochées. Le rang n'est lu que sur les racines ; sur les autres nœuds, c'est une trace périmée qu'on ne prend pas la peine d'effacer.

Le nombre d'éléments confirme la proposition du chapitre : rang $3$, donc au moins $2^3=8$ éléments — et il y en a exactement $8$. Le tournoi est le pire cas de l'union par rang, celui où la borne est atteinte (exercice « La borne ${\log }_{2}n$ est atteinte »).