Le rang ment, et c'est voulu

1. L'appel remonte $7\to 6\to 4\to 0$ et raccroche $7$ et $6$ directement à $0$ :

avant : parent = [| 0; 0; 0; 2; 0; 4; 4; 6 |]   hauteur 3, rang[0] = 3
apres : parent = [| 0; 0; 0; 2; 0; 4; 0; 0 |]   hauteur 2, rang[0] = 3

La hauteur mesurée est tombée de $3$ à $2$ ; le rang, lui, n'a pas bougé. Après compression, le rang n'est donc plus la hauteur : c'en est seulement une majoration.

2. Parce que corriger coûterait plus cher que ce que la correction rapporte, et pour deux raisons distinctes.

D'abord, on ne saurait pas quoi écrire : recalculer la hauteur exacte d'un arbre demande de le parcourir entièrement, donc $\Theta (\text{taille})$ — alors que tout l'intérêt de trouver est de ne toucher qu'un chemin.

Ensuite, on n'en a pas besoin. Ce que la proposition du chapitre exige est une majoration : « un arbre de rang $r$ contient au moins $2^r$ éléments », donc $r\le {\log }_{2}n$. Cette majoration reste vraie après compression, puisque la compression ne change ni le nombre d'éléments ni le rang. La hauteur réelle ne peut que diminuer, donc rester sous ${\log }_{2}n$ : la borne tient toujours.

La leçon générale. Une donnée auxiliaire n'a pas à être exacte : elle doit être exploitable. Ici, le rang est une majoration paresseuse de la hauteur, entretenue en $O(1)$, et c'est tout ce dont la preuve a besoin. Vouloir l'exactitude aurait ruiné la structure.