AVL tree rotation

I'm trying to create AVL tree. So, a started with a binary tree and added a height value to it. Now, i'm trying to make the left and right rotations so it can balance itself. The binary tree and height value works fine, but i can't get the left rotate to work, and i'm a little confused about the psuedocode for it.
I was trying to follow this psuedocode from the book:

Code:

---

LEFT-ROTATE(T, x)
y<-right[x]
right[x]<-left[y]
if left[y] != nil[T]
  then p[left[y]]<-x
p[y]<-p[x]
if p[x] = nil[T]
  then root[T]<-y
  else if  x = left[p[x]]
              then left[p[x]] = y
              else right[p[x]] = y
left[y]<-x
p[x]<-y

---

where T is the tree and x is the node the rotation is done on.
For the nil[T], is this just suppose to be NULL?
And, i'm not sure what is suppose to go here:

Code:

---

then root[T]<-y

---

So, i'm a little unclear about the T in this code. It has T as a parameter, but i don't understand how you pass in the whole tree.
Here is what i have (it doesn't work correctly)

Code:

---

int LeftRotate(candidate *root, candidate *x)
{
        candidate *y;
        y = x->right;
        x->right = y->left;

        if(y->left != NULL)
        {
                y->left->parent = x;
        }

        y->parent = x->parent;

        if(x->parent == NULL)
        {
                root = y;
        }
        else if(x = x->parent->left)
        {
                x->parent->left = y;
        }
        else
        {
                x->parent->right = y;
        }

        y->left = x;
        x->parent = y;

        return 0;
}

---

Here is my main:

Code:

---

int main(int argc, char* argv[])
{
        ifstream inFile ( argv[1] );

        if ( !inFile.is_open() )
        {
                cout << "Could not open file." << endl;
        }
        else
        {
                char name[20];
                int count = 0;

                candidate *root;
                root = NULL;


               
                while(!inFile.eof())
                {
                        //Flag determines if name has been found in search.
                        int flag = 0;
                                                       
                        inFile.getline(name, 20);
                        //Change all upper-case letter to lower-case, so they will count as the same name.
                        LowerCase(name, count);

                        //If name is already in tree, increase votes.
                        TreeSearch(root, name, flag);
                       
                        //If name is not already in tree, insert it.
                        if(flag == 0)
                        {
                                TreeInsert(root, name, flag);
                        }                       
                }

                //Make copy of original root
                candidate *root2;
                root2 = root;               
                               
                LeftRotate(root2, root);               
                cout << endl;


                cout << endl;
                //Print tree in-order (alphabetical).
                PrintTree(root);               
        }       

        cin.get();
        return 0;
}

---

Everything in and above the while loop is fine.
I thought maybe i was suppose to send in the root of the tree along with the node being rotated, so i duplicated the root node, and passed it in, but i guess that's not correct. So, all the code that is red, i'm not sure what i should be putting there. Any suggestions on how to fix this function?

Thanks

PS: If it looks familiar, it's the same as my hash program, except i'm using an AVL tree instead of a hash table.

>else if(x = x->parent->left)
Here's a useful tip: Think of = as the "is now" operator. Is x equal to x->parent->left? It is now! ;)

>I was trying to follow this psuedocode from the book
I never liked the pseudocode examples from that book. If you don't mind me tooting my own horn, here's a tutorial on AVL trees using C that you might find more accessible.

">else if(x = x->parent->left)
Here's a useful tip: Think of = as the "is now" operator. Is x equal to x->parent->left? It is now! "

I must have read that ten times before i caught my mistake :) .
I fixed that, but it still doesn't work. Now, If i call the function like:

Code:

---

LeftRotate(root2, root);

---

I lose what would be the new root, and every name in its right subtree.
If i call the function like:

Code:

---

LeftRotate(root2, root->right);

---

I lose everything, and nothing prints.

Do read Prelude's AVL tree tutorial, they're quite good as many of us here will vouch for.

Since you appear to be using root as an output parameter of LeftRotate, you'll need to make sure that the function takes a reference to a pointer, so that you can change what it points to.

Ya, i tried changing it to a reference, but that didn't work either. But, i now have another rotate algorithm that works and contains less lines of code.

Now, i have one last question (i hope). My tree is not being balanced correctly, and i'm not sure why. Here is my code:

Code:

---

int TreeInsert(candidate *&root, string name, int &flag)
{
        candidate *y = NULL;
        candidate *x = root;

        candidate *z;
        z = new candidate;
        z->firstName = name;
        z->votes = 1;
        z->right = NULL;
        z->left = NULL;
        z->height = 0;

        while(x != NULL)
        {
                y = x;

                if(z->firstName < x->firstName)
                {
                        x = x->left;
                }
                else
                {
                        x = x->right;
                }
        }

        z->parent = y;       

        if(y == NULL)
        {
                root = z;               
        }
        else if(z->firstName < y->firstName)
        {
                y->left = z;
        }
        else
        {
                y->right = z;
        }       
               
        BalanceTree(root);

        return 0;
}

---

Code:

---

int BalanceTree(candidate *&root)
{
       
        FindHeight(root);
        FindBalance(root);
       
        //Right heavy
        if(root->balance == 2)
        {       

                if( root->right->balance == -1)
                {
                        cout << "Double rotate left call" << endl;
                        SingleRotateRight(root->right);
                        SingleRotateLeft(root);
                }
                else
                {
                        cout << "Single roate left call" << endl;
                        SingleRotateLeft(root);
                }
        }
        //Left heavy
        else if(root->balance == -2)
        {               
                if( root->left->balance == 1)
                {
                        cout << "Double rotate right call" << endl;
                        SingleRotateLeft(root->left);
                        SingleRotateRight(root);

                }
                else
                {
                        cout << "Single rotate right call" << endl;
                        SingleRotateRight(root);
                }
        }
       
        return 0;
}

---

Now, I'm pretty sure that my right and left rotations are working correctly. I made a file with just a few names that were inserted so that it is like a linked list. When the program is finished it is not balanced correctly. I think this is what it is doing:

Code:

---

                            Marry                      Clint
                        Larry                        Bill    John
                      John          =          Aztec            Lary
                  Clint                      Adam                    Marry
                Bill
            Aztec
        Adam

---

It's balancing the root every time, so the root ends up balanced. But, the other nodes do not end up balanced (Bill and John). I thought by adding the BalanceTree call in my insert function, it would balance everything correctly. I also tried moving the BalanceTree call to main, but i get the same results.
On another file, where the names are inserted randomly, the root doesn't end up balanced, so maybe there is another problem.

Any help would be appreciated.
Thanks

The problem is that you're doing the insertion iteratively. You need to either do it recursively with a BalanceTree call in each recursive call, or use some other form of trickyness like parent pointers, or an explicit stack.

Do you mean i can't do it in the insert function?
I still can't figure it out. I tried replacing (in the insert function):

Code:

---

BalanceTree(root);

---

with:

Code:

---

while(z->parent != NULL)
{
    z = z->parent;
    BalanceTree(z);
}

---

I thought this should balance every node from z (the inserted node) up till the root node.
But, when i run the program, only the root prints. So, it's like the tree is not linked together anymore or something.

I also tried BalanceTree(z) at the end of the insert function, and adding:

Code:

---

if(root->parent != NULL)
{
    root = root->parent;
    BalanceTree(root);
}

---

at the end of the BalanceTree function.
So, i thought it should call itself recursively and balance every node from z (the inserted) untill the root. But i get the same result as above.

Edit* - I also tried calling BalanceTree recursively with its parent every time. I added:

Code:

---

BalanceTree(z);

---

to the end of the insert function, and:

Code:

---

if(root->parent != NULL)
{
    BalanceTree(root->parent);
}

---

at the end of the BalanceTree function. So, i thought this should balance z, and all its parents up to the root, but no names print at all.

Any ideas?
Thanks

Quote:

---

Originally Posted by Cpro

Do you mean i can't do it in the insert function?
I still can't figure it out. I tried replacing (in the insert function):

Code:

---

BalanceTree(root);

---

with:

Code:

---

while(z->parent != NULL)
{
    z = z->parent;
    BalanceTree(z);
}

---

---

For that to work I think you'd need to declare z as a reference. I'd have to try it out myself though.

Quote:

---

I thought this should balance every node from z (the inserted node) up till the root node.
But, when i run the program, only the root prints. So, it's like the tree is not linked together anymore or something.

I also tried BalanceTree(z) at the end of the insert function, and adding:

Code:

---

if(root->parent != NULL)
{
    root = root->parent;
    BalanceTree(root);
}

---

at the end of the BalanceTree function.
So, i thought it should call itself recursively and balance every node from z (the inserted) untill the root. But i get the same result as above.

---

Nope you shouldn't have to touch the BalanceTree function.

Quote:

---

Edit* - I also tried calling BalanceTree recursively with its parent every time. I added:

Code:

---

BalanceTree(z);

---

to the end of the insert function, and:

Code:

---

if(root->parent != NULL)
{
    BalanceTree(root->parent);
}

---

at the end of the BalanceTree function. So, i thought this should balance z, and all its parents up to the root, but no names print at all.

---

It's TreeInsert that needs to be made recursive if you want to do the recursive solution, not BalanceTree. I've only done the recursive solution, and haven't made one that uses parent pointers. Parent pointers can aid in traversing back up the tree, but at the cost of adding more complexity to the tree rebalancing.

I would recommend writing a tree-verification routine (an invariant checker) that you can call at specific times like before and after a rebalance to check that the tree is in a good state.
Such a verification routine could recursively check the following:
Left pointer is either NULL or
Left pointer points to a node whose value is not greater than the current node.
Left pointer's parent is this node.
Left node's height is the parent node's height minus 1
Right pointer is either NULL or
Right pointer points to a node whose value is not less than the current node.
Right pointer's parent is this node.
Right node's height is the parent node's height minus 1
You could even count all the nodes too.

That should make debugging a lot easier!

VICTORY !
I got it working. Thanks for all the help and explanations.
I really appreciate it!