Updating an AVL Tree Based On Balance Factors

I'm looking at the lecture review for one of my computer science classes and I'm having trouble coming up with an answer. Could someone help me work through it?

Background:

Let the balance factor of a node be defined by $\left| height(\text{right sub tree}) - height(\text{left sub tree}) \right|$.

Questions:

• Give the balance factor for the nodes in slides 27-30 (given below)

• Instead of storing the heights of the nodes, can we store the balance factors of the nodes and update an AVL tree (for insertion and deletion) based on this information?

Here are the relevant slides:

I will answer the second question.


Instead of storing the heights of the nodes, can we store the balance factors of the nodes and update an AVL tree (for insertion and deletion) based on this information?

Yes, actually that's the whole idea behind the avl tree. All balance factors are always in range [-1, 1], so you need only two extra bits per node to store it.

After insertion you simply climb up the tree and update balance factors:

• decrease if the left sub-tree became higher,

• increase if the right sub-tree became higher,

• retrace the tree if the balance factor becomes -2 or 2 (this can be achieved by local rotations on the tree),

• if balance factor becomes 0, then the tree became balanced and no further work is required.

For more details check wikipedia page.

If you need more mathematical analysis on how the balance factors change after local rotations, check my question/answer here.

StackExchange Computer Science Q#16313, answer score: 3