Discussion :

[crischprolch]

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

[ToTo13]

Bonjour,
de mémoire c'est ce que l'on ma enseigné durant mes cours.
donc algo correcte.

[crischprolch]

mon interrogation se porte surtout sur l'endroit que je dois mémoriser pour faire les mise à jour (rotations). Je pense qu'il faille sauver le dernier noeud de desequilibre nul mais est-ce que ça me garantit que je n'aurai pas besoin de propager les modifications plus haut ? Je rappelle que je fais des mises à jour en descendant(à gauche ou à droite en fonction de la valeur supprimée).

merci

[Graffito]

Bonjour,

A priori, stocker le dernier noeud à déséquilibre nul ne me semble pas suffisant. En effet, la réorganisation d'un sous-arbre peut conduire à diminuer sa profondeur et à créer un déséquilibre avec son frére.

Si ce raisonnement est vrai, il faudrait non seulement que le noueud stocké soit à déséquilibre nul, mais que tous ses parents soient aussi à déséquilibre nul.

[Graffito]

Rebonjour,

Mon message peut sembler confus car j'ai raisonné sur l'équilibre des profondeurs et pas sur celle des poids. Mais il me semble que le raisonnement reste aussi valable pour les poids.

[crischprolch]

merci,
il me semblait aussi que ce ne soit pas suffisant ...