Recalcul du facteur équilibre dans AVL arbre

Question

Après avoir effectué une rotation pour équilibrer un arbre AVL, immédiatement après l'insertion, comment modifier le facteur d'équilibre de l'ensemble des noeuds parents (de manière appropriée, par -1 ou 1)?

Chaque noeud 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 besoin d'avoir un pointeur vers le nœud parent dans chaque noeud?

Answer 1

Vous avez besoin soit un pointeur parent pour chaque noeud, qui aura besoin de modification trop à chaque fois que vous modifiez la structure de l'arbre. Ou vous avez besoin de garder une trace de tous les nœuds visités commençant à partir de la racine, soit automatiquement par la récursion ou 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

ont peut-être un regard sur AVL C Bibliothèque d'inspiration?