Rééquilibrage

Les rotations vont servir à maintenir l'équilibre de chaque noeud. Nous allons nous intéresser à l'équilibre d'un arbre de racine $v$ dont les deux sous-arbres ($G$ et $D$) sont équilibrés, et ont des hauteurs qui diffèrent de $2$. Supposons, sans perte de généralité, que $h(D) = n$, et que $h(G) = n + 2$. Soit $G = (B, y, D)$, alors deux cas se présentent :

• si $h(B) = n + 1$, alors une rotation droite de $v$ équilibre l'arbre.
• si $h(B) \not = n + 1$, alors une rotation gauche-droite de $v$ équilibre l'arbre.