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.
if left[y] != nil[T]
if p[x] = nil[T]
else if x = left[p[x]]
then left[p[x]] = y
else right[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.
Here is what i have (it doesn't work correctly)
Here is my main:
int LeftRotate(candidate *root, candidate *x)
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;
x->parent->right = y;
y->left = x;
x->parent = y;
Everything in and above the while loop is fine.
int main(int argc, char* argv)
ifstream inFile ( argv );
if ( !inFile.is_open() )
cout << "Could not open file." << endl;
int count = 0;
root = NULL;
//Flag determines if name has been found in search.
int flag = 0;
//Change all upper-case letter to lower-case, so they will count as the same name.
//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
root2 = root;
cout << endl;
cout << endl;
//Print tree in-order (alphabetical).
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?
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.