Solution du TD7 sur les AVL #

Tout d’abord on s’assure que les rotations présèrvent le fait d’être un arbre binaire de recherche.

On fournit le code des rotations.

On calcule les hauteurs des nœuds de l’arbre

On explique la formule générale permettant de les calculer

On indique le déséquilibre sur les noeuds de l’arbre

On explique les noeuds sur lesquels le déséquilibre doit être recalculé

On montre qu’un arbre ne peut pas être totalement équilibré pour n’importe quel nombre de noeuds. Trouvez la boulette.

On illustre finalement l’insertion successive de valeurs dans un AVL et les rééquilibrages résultants