Discussion :

[awadj]

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 !

[SpiceGuid]

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.

[awadj]

C'est la solution que j'ai mise en oeuvre depuis hier et ça marche, je pensais qu'on pouvait faire mieux mais j'ai au moins certitude que non.

Merci !