Algo de Suppression dans un AVL
Bonsoir à tous.
Je me présente à vous car j'ai un petit soucis d'algorithmique sur les AVL.
Les AVL ce sont des Arbres Binaires de Recherches qui ont la particularité d'être équilibrés. (Chaque Noeud vérifie la propriété : Equilibre = Hauteur du fils gauche - Hauteur du fils droit = -1 ou 0 ou 1)
En ce qui concerne l'algo. d'insertion, en voici un résumé pour vous faire une idée :
-On cherche où l'on va insérer le nouveau noeud s'il n'existe pas déjà.
-Des qu'une place est libre a un endroit correspondant, on insère le noeud.
-Lorsqu'on parcours l'arbre pour chercher une nouvelle position, on retient le dernier noeud avec un équilibre différent de 0.
-Après insertion, on test l'équilibre du Noeud cité juste au dessus. En fonction de ce qu'il vaut on effectue un rééquilibrage (une rotation gauche, droite, gauche-droite ou droite-gauche) ou rien si son equilibre vaut toujours -1 ou 0 ou 1.
Ici ma question est : Pour l'algorithme de Suppression, quel Noeud dois-je retenir pour effectuer mon rééquilibrage (mes rotations donc) ?
Merci d'avance !
tous les noeuds sur le chemin
Citation:
Pour l'algorithme de Suppression, quel Noeud dois-je retenir pour effectuer mon rééquilibrage (mes rotations donc) ?
Tu dois retenir la totalité du chemin, tester tous les noeuds sur ce chemin et les rééquilibrer si nécessaire. Dans le cas de l'insertion il y a un seul rééquilibrage au plus. Dans le cas de la suppression tout noeud sur le chemin qui conduit au noeud supprimé est susceptible de donner lieu à un rééquilibrage.
La façon la plus simple de mémoriser la totalité du chemin c'est de coder la recherche du noeud de façon récursive au lieu de façon itérative.
