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