Recalcul du facteur d'équilibre dans l'arbre AVL

Question

Après avoir effectué une rotation pour équilibrer un arbre AVL, immédiatement après une insertion, comment puis-je modifier le facteur d'équilibre de tous les nœuds parents (de manière appropriée, par -1 ou 1)?

Chaque nœud de l'arbre AVL a la structure suivante:

typedef struct _avlTree 
{ 
nutbolt part; 
int balanceFactor; 
struct _avlTree *left,*right; 
} *avlTree; 

J'ai mis le facteur d'équilibre selon la définition donnée sur Wikipedia. Dois-je avoir un pointeur sur le nœud parent de chaque nœud?

Answer 1

Vous avez besoin d'un pointeur parent pour chaque noeud, ce qui nécessitera également des modifications lorsque vous modifiez la structure arborescente. Ou vous devez garder une trace de tous les nœuds visités à partir de la racine, soit automatiquement par la récursion, soit manuellement dans un tableau si vous avez une approche itérative.

Vous ne devriez pas manquer pour une étude approfondie du sujet:

http://www.stanford.edu/~blp/avl/

Answer 2

Peut-être jeter un oeil à AVL C Library pour l'inspiration?