Thread: AVL tree rotation

  1. #1
    Registered User Cpro's Avatar
    Join Date
    Oct 2006
    Posts
    149

    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.
    IDE - Visual Studio 2005
    Windows XP Pro

  2. #2
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,897
    >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.
    My best code is written with the delete key.

  3. #3
    Registered User Cpro's Avatar
    Join Date
    Oct 2006
    Posts
    149
    ">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.
    IDE - Visual Studio 2005
    Windows XP Pro

  4. #4
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    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.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  5. #5
    Registered User Cpro's Avatar
    Join Date
    Oct 2006
    Posts
    149
    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
    IDE - Visual Studio 2005
    Windows XP Pro

  6. #6
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    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.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  7. #7
    Registered User Cpro's Avatar
    Join Date
    Oct 2006
    Posts
    149
    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
    Last edited by Cpro; 03-25-2008 at 10:26 PM.
    IDE - Visual Studio 2005
    Windows XP Pro

  8. #8
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Quote Originally Posted by Cpro View Post
    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.
    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.
    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!
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  9. #9
    Registered User Cpro's Avatar
    Join Date
    Oct 2006
    Posts
    149
    VICTORY !
    I got it working. Thanks for all the help and explanations.
    I really appreciate it!
    Last edited by Cpro; 03-26-2008 at 07:36 PM.
    IDE - Visual Studio 2005
    Windows XP Pro

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Interpreter.c
    By moussa in forum C Programming
    Replies: 4
    Last Post: 05-28-2008, 05:59 PM
  2. Binary Tree, couple questions
    By scoobasean in forum C Programming
    Replies: 3
    Last Post: 03-12-2005, 09:09 PM
  3. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 10:33 AM
  5. BST/Red and Black Tree
    By ghettoman in forum C++ Programming
    Replies: 0
    Last Post: 10-24-2001, 10:45 PM