balance Arbre AVL avant ou après la suppression du noeud?

Question

Cet exercice demande à l'étudiant de supprimer un noeud d'un arbre AVL. Dans ce cas, cela nécessite un certain équilibrage, puisque la différence entre la profondeur la plus profonde et la profondeur la plus faible est> 1. Mais l'équilibrage devrait-il avoir lieu avant ou après la suppression? Ou n'est-ce pas important?

image of AVL tree in question

Answer 1

Essentiellement, vous voulez supprimer comme vous le feriez d'un BST. Puis calculez votre facteur de profondeur (combien de temps chaque chemin de l'arbre est) et faites des rotations comme vous le feriez normalement avec des inserts en fonction des chemins qui sont déséquilibrés. Donc, pour répondre à votre question, vous faites les rotations après avoir supprimé.