Recalculation of Balance Factor in AVL Tree

Question

After performing a rotation to balance an AVL tree, immediately after an insertion, how can I change the balance factor of all the parent nodes (appropriately, by -1 or 1)?

Each node of the AVL tree has the following structure:

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

I have set the balance factor as per the definition given on Wikipedia.

Do I need to have a pointer to the parent node in each node?

Answer 1

Maybe have a look at AVL C Library for inspiration?

Answer 2

You either need a parent pointer for each node, which will need modification too whenever you change the tree structure. Or you need to keep track of all visited nodes beginning from the root, either automatically by the recursion or manually in an array if you have an iterative approach.

You shouldn't miss this for an in-depth study of the topic:

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