1. 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.

2. You know how to rotate based on how the balance factors are set. My tutorial describes all of this, including the specific cases you need to look for and how to respond to them. What in particular are you having trouble with?

>This whole thing is confusing as heck.
It's a complicated data structure, what did you expect?

3. 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.

4. >My first problem is exactly how to figure out the balance factors for each node.
The most straightforward way is to do it after you insert each node. Walk back up the path and adjust balance factors.

>Could I use this function to update the balance factors?
It probably wouldn't be worth it.

5. Bear in mind that you never actually calculate the entire balance factor for a node from scratch. You only ever need to adjust it acording to the changes that you make to the tree which you know affected the balance by a certain amount.

You wont really find it any easier rebalancing as an second pass either. You would either end up rebalancing the entire tree or you follow the path down where the node you inserted goes. However during insertion you do the same thing so you may as well just rebalance the node after each recursive call.

There are two ways to do an AVL tree though. One is to store a balance factor in each node, the other is to store the height in each node.

My website doesn't really explain the algorithms as such yet, but the fairly well written and hopefully understandable implementations (if I do say so myself) are there for you to study. (Link in sig)

6. 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))
{
}
else
{
}
}
}```
Where/how to set height member?

7. Ok cool.
I think probably the next step is to do some drawings on paper of the unbalanced tree cases, and then draw what the rotation will change it to, and then step through what has changed and write the code to do it. At least that's the kind of thing that helped me when I was doing it. It'll definitely help to refer to Prelude's article as well though to make sure you stay on track.

8. On prelude's website:
Code:
`if (lh - rh >= 2 )`
Is supposed to know when a tree is out of balance?
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?

9. [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]