Thread: Making an AVL Tree

Hello,

I need some guidance regarding AVL Trees. So far, I have created a binary tree library. For the next step, I want to use this btree source code to make it into an AVL tree. I have studied Prelude's AVL Tutorial on her webpage and I understand the rotations part. However, I need some assistance on how to know when to do a rotation. I know I need to add a "balance" variable to each node. Also that I need to modify my insert function to automatically perform rotations. I plan to insert normally, then do a tree traversal that will update balance factors. When out of balance is detected I run a rotation but how do I know which one is needed (single, double, left, right) ?

This whole thing is confusing as heck.

Hi Prelude.

Your tutorial is awesome I learned a lot from it. I want to use the bounded balance factors method as it seems a fair bit easier (I can worry about efficency later). My first problem is exactly how to figure out the balance factors for each node. I have a function Tree_traversal that allows a function to be passed in that will be called in either pre, post or inorder, eh, order. Could I use this function to update the balance factors? Or do I need to create a specific function for rebalance(Tree *)?

I'm sure if I spend enough time with your tut, I could do this. I understand all the the code, it's pretty simple for me. However, I don't want to cut and paste I want to create my own version using my already written library of code.

Ok, so far I've got all the rotation functions written and tested. Took me a couple hours of debugging though. I added a height member to my nodes. Next I would like to modify my insertion function so that it will update the heights. After that, I can worry about checking balances and how to call the right rotations.

Code:

void BSTree_add(struct Tree *pTree, int value)
{
  if (Tree_isempty(pTree))
  {
    Tree_setrootvalue(pTree, value);
  }
  else
  {
    if (value <= Tree_getrootvalue(pTree))
    {
      BSTree_add(Tree_getlefttree(pTree), value);
    }
    else
    {
      BSTree_add(Tree_getrighttree(pTree), value);
    }
  }
}

Where/how to set height member?

On prelude's website:

Code:

if (lh - rh >= 2 )

Is supposed to know when a tree is out of balance?
What about this tree?

Code:

1, 2
 \
  2, 1
   \
    3, 0

Lets see, I know I need to perform a left rotation at (1), but I don't think that condition above would be true. Let's see: LH = -1, RH = 1. (-1 - 1) == 0. Am I missing something?

[EDIT]

WOOT!

Got it completely working now! I thought I'd never be able to do it.

Thanks for writing such a great tutorial prelude: even if I didn't use your code (and I realised my framework was overly-complex) the concepts were described in general enough terms that I was able to figure it out.

[/EDIT]