bonjour,
je dois écrire un programme qui supprime un element dans un arbre binaire de recherche équilibré. Pour ce faire, j'ai accés au deséquilibre pour chaque noeud (en fait mes elements sont des couples <valeur,desequilibre>. Je dois faire ce travail itérativement, et je pense qu'il faille faire comme suit :
Tout d'abord, descendre le long de l'arbre pour trouver l'endroit où est l'element e (on fait filsGauche si e<racine , filsDroit sinon) et en meme temps, on mémorise le dernier sous-arbre (a) de désequilibre nul (pour pouvoir faire des rotations à partir de là et ainsi équilibrer le reste de l'arbre). Ensuite, on supprime e en le remplaçant par le maximum de son filsGauche. Puis on part de a en on descend en mettant à jour les deséquilibres de chaque noeud par où l'on passe (+1 si e>racine, -1 sinon car on supprime un élement). dès qu'on a un desequilibre de + ou - 2, on fait des rotations adéquates (ke je ne détailleraient pas car je les ai et elles fonctionnent sur la fonction d'ajout...), et ceci jusqu'à ce que l'arbre a soit vide.
ma question est de savoir si cet algo est correct.
merci
Partager