Exercices (pc 6)

Exercice 1 Ecrire les fonctions qui effectuent une rotation droite ou gauche sur un arbre binaire.

Exercice 2 Une double rotation droite est une rotation gauche sur le sousarbre gauche suivie d’une rotation droite. La même notion vaut mutatis mutandis à gauche.

Ecrire les fonctions réalisant les doubles rotations gauche et droite.

Exercice 3 On note

δ(r, S, T) = h(T) − h(S)

le déséquilibre d’un arbre binaire.

Ecrire la fonction d’insertion d’un élément dans un arbre AVL en utilisant une fonction de réquilibrage définie sur un arbre T = (r, R, S) par

ρ(T) = \{ \begin{matrix}rotG(T) & si δ(T) = 2 & et δ(S) ≥ 0 \\ drotG(T) & si δ(T) = 2 & et δ(S) = −1 \\ rotD(T) & si δ(T) = −2 & et δ(R) ≤ 0 \\ drotD(T) & si δ(T) = −2 & et δ(R) = 1 \\ T & si δ(T) ∈ \{−1, 0, 1\} \end{matrix}