3
$\begingroup$

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:

  1. Give the balance factor for the nodes in slides 27-30 (given below)
  2. 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:

enter image description here enter image description here enter image description here enter image description here

$\endgroup$
  • 1
    $\begingroup$ Do you really have 2 questions, or are you only interested in question #2? $\endgroup$ – Realz Slaw Oct 21 '13 at 19:44
  • 1
    $\begingroup$ See this presentation, starting page 11. It described insertion. This presentation might also be helpful. $\endgroup$ – Realz Slaw Oct 21 '13 at 22:40
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.