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:

where T is the tree and x is the node the rotation is done on.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

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.Code:then root[T]<-y

Here is what i have (it doesn't work correctly)

Here is my main: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; }

Everything in and above the while loop is fine.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; }

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.