Exercice 4 - Suppression

On notera

• $succ_A(x)$ le successeur de $x$ dans $A$, c'est-à-dire l'élément de $A(x)$ de plus petite clé parmi les éléments de clé supérieure à celle de $x$.
• $premier(A(x))$ le plus petit élément de $A(x)$

1. Prouvez que si un noeud $x$ d'un arbre $A$ a deux fils, alors $succ_A(x)$ n'a pas de fils gauche.
2. Montrez que $y = succ_A(x)$ si et seulement si $y = premier(A_d(x)$ ou $x = dernier(A_g(y))$.
3. Supprimez la racine de l'arbre de l'exercice précédent