Results 1 to 12 of 12

Thread: Left / Right rotate

  1. #1

    Thread Starter
    PowerPoster sunburnt's Avatar
    Join Date
    Feb 2001
    Location
    Boulder, Colorado
    Posts
    1,403

    Left / Right rotate

    I'm working on a splay tree implementation for my Algorithms class. We were given the following psuedo code for a Left rotation:
    Code:
    Left-Rotate(T,x)
    1	y <-- right[x]	//Set y
    2	right[x] <-- left[y]	//Turn y's left subtree into x's right subtree
    3	if left[y] != NIL
    4	  then p[left[y]] <-- x
    5	p[y] <-- p[x]	//Link x's parent to y
    6	if p[x] = NIL
    7		then root[T] <-- y
    8	else if x = left[p[x]]
    9		then left[p[x]] <-- y
    10		else right[p[x]] <-- y
    11	left[y] <-- x		// Put x on y's left
    12	p[x] <-- y
    which I translated as

    Code:
    void SplayTree::left_rotate(Node* x)
    {
    	Node* y = x->right;
    	x->right = y->left;
    
    	if (y->left)
    		y->left->p = x;
    
    	y->p = x->p;
    
    	if (!x->p)
    		this->root_ptr = y;
    	else if (x == x->p->left)
    		x->p->left = y;
    	else
    		x->p->right = y;
    
    	y->left = x;
    	x->p = y;
    }
    I don't really understand what it's doing, (I do graphically, but not code wise -- it just seems like a bunch of random deattachments and attachments.) but I followed the algorithm so my code should be correct. Can anyone a) try to explain what's going on in order to b) help me implement the right_rotate function.

    Thanks.
    Every passing hour brings the Solar System forty-three thousand miles closer to Globular Cluster M13 in Hercules -- and still there are some misfits who insist that there is no such thing as progress.

  2. #2
    transcendental analytic kedaman's Avatar
    Join Date
    Mar 2000
    Location
    0x002F2EA8
    Posts
    7,221
    If i'm right, whats confusing you are the pointers, because thats what most gets hung up on. I suggest you use the graph as a starting point when both analysing the left rotation and implementing the right rotation.

    As for the pointers, in your graph draw draw a black dot at the top of each edge marking the owner of the pointer, which in this case should be the parent node, that contain its right and left references. When you assign a pointer, the lose end (the end that doesn't have a dot) is refered to another node. When you assign a pointer to null, the pointer lacks reference.
    Use
    writing software in C++ is like driving rivets into steel beam with a toothpick.
    writing haskell makes your life easier:
    reverse (p (6*9)) where p x|x==0=""|True=chr (48+z): p y where (y,z)=divMod x 13
    To throw away OOP for low level languages is myopia, to keep OOP is hyperopia. To throw away OOP for a high level language is insight.

  3. #3
    Kitten CornedBee's Avatar
    Join Date
    Aug 2001
    Location
    In a microchip!
    Posts
    11,594
    Maybe this helps you, it's my C# implementation of all four rotate functions. This is for an AVL tree.

    Code:
    /// <summary>
    /// Recalculates the height of a node.
    /// </summary>
    /// <param name="node">The node for which to recalculate the height.</param>
    private void AdjustHeight(TreeNode node)
    {
    	if(node.left == null && node.right == null)
    	{
    		node.height = 0;
    	}
    	else
    	{
    		int lw = node.left == null ? 0 : node.left.height;
    		int rw = node.right == null ? 0 : node.right.height;
    		node.height = Math.Max(lw, rw) + 1;
    	}
    }
    
    /// <summary>
    /// Helper method for rebalancing. Does a right rotation.
    /// </summary>
    /// <param name="node">On entry the unbalanced node. On exit the node in its place.</param>
    private void RotateRight(ref TreeNode node)
    {
    	TreeNode t = node.left;
    	node.left = t.right;
    	if(node.left != null)
    		node.left.parent = node;
    	t.right = node;
    	if(t.right != null)
    		t.right.parent = t;
    	t.parent = node.parent;
    	AdjustHeight(node);
    	AdjustHeight(t);
    	node = t;
    }
    
    /// <summary>
    /// Helper method for rebalancing. Does a left-right rotation.
    /// </summary>
    /// <param name="node">On entry the unbalanced node. On exit the node in its place.</param>
    private void RotateLeftRight(ref TreeNode node)
    {
    	RotateLeft(ref node.left);
    	RotateRight(ref node);
    }
    
    /// <summary>
    /// Helper method for rebalancing. Does a left rotation.
    /// </summary>
    /// <param name="node">On entry the unbalanced node. On exit the node in its place.</param>
    private void RotateLeft(ref TreeNode node)
    {
    	TreeNode t = node.right;
    	node.right = t.left;
    	if(node.right != null)
    		node.right.parent = node;
    	t.left = node;
    	t.parent = node.parent;
    	if(t.left != null)
    		t.left.parent = t;
    	AdjustHeight(node);
    	AdjustHeight(t);
    	node = t;
    }
    
    /// <summary>
    /// Helper method for rebalancing. Does a right-left rotation.
    /// </summary>
    /// <param name="node">On entry the unbalanced node. On exit the node in its place.</param>
    private void RotateRightLeft(ref TreeNode node)
    {
    	RotateRight(ref node.right);
    	RotateLeft(ref node);
    }
    A TreeNode has the members:
    parent: parent node (for iteration over the tree)
    left: left child node
    right: right child node
    height: maximum subtree height (for balancing)
    All the buzzt
    CornedBee

    "Writing specifications is like writing a novel. Writing code is like writing poetry."
    - Anonymous, published by Raymond Chen

    Don't PM me with your problems, I scan most of the forums daily. If you do PM me, I will not answer your question.

  4. #4
    Kitten CornedBee's Avatar
    Join Date
    Aug 2001
    Location
    In a microchip!
    Posts
    11,594
    Just came up with a better AdjustHeight implemenation:
    Code:
    private void AdjustHeight(TreeNode node)
    {
    	int lw = node.left == null ? -1 : node.left.height;
    	int rw = node.right == null ? -1 : node.right.height;
    	node.height = Math.Max(lw, rw) + 1;
    }
    All the buzzt
    CornedBee

    "Writing specifications is like writing a novel. Writing code is like writing poetry."
    - Anonymous, published by Raymond Chen

    Don't PM me with your problems, I scan most of the forums daily. If you do PM me, I will not answer your question.

  5. #5

    Thread Starter
    PowerPoster sunburnt's Avatar
    Join Date
    Feb 2001
    Location
    Boulder, Colorado
    Posts
    1,403
    Unfortunantly I haven't gotten this to work yet. It's due in three days and I'm still struggling to implement it. As of now there are no errors or blow ups, but my trees are coming out all screwed up. I assume this is a problem with my rotate functions (as the splay() function shouldn't change any node ordering directly), but I'll be damned if I can see it. Example of the screwup below the code.

    Code:
    void SplayTree::left_rotate(NodePointer x)
    {
    	++left_rotates;
    
    	NodePointer y = x->right;
    	x->right = y->left;
    	if (y->left)
    		y->left->p = x;
    
    	y->p = x->p;
    	if (!x->p)
    		root_ptr = y;
    	else if (x == x->p->left)
    		x->p->left = y;
    	else
    		x->p->right = y;
    
    	y->left = x;
    	x->p = y;
    
    	if (y->left)
    		y->left->p = y;
    	
    }
    
    void SplayTree::right_rotate(NodePointer x)
    {
    	++right_rotates;
    
    	NodePointer y = x->left;
    	x->left = y->right;
    	if (y->right)
    		y->right->p = x;
    
    	y->p = x->p;
    	if (!x->p)
    		root_ptr = y;
    	else if (x == x->p->left)
    		x->p->left = y;
    	else
    		x->p->right = y; 
    
    	y->right = x;
    	x->p = y;
    
    	if (y->right)
    		y->right->p = y;
    
    }
    
    
    void SplayTree::splay(NodePointer x)
    {
    	NodePointer y, z;
    
    	if (!x)
    		return;
    
    	while(x != root_ptr)
    	{
    		// y = parent, z = grandparent
    		y = x->p;
    		if (!y)
    			z = NULL;
    		else
    			z = y->p;
    
    		if (x == root_ptr->left)
    			right_rotate(root_ptr);
    		else if (x == root_ptr->right)
    			left_rotate(root_ptr);
    		else if (x == y->left && y == z->left)
    		{
    			right_rotate(z);
    			right_rotate(y);
    		}
    		else if (x == y->right && y == z->right)
    		{
    			left_rotate(z);
    			left_rotate(y);
    		}
    		else if (x == y->right && y == z->left)
    		{
    			left_rotate(y);
    			right_rotate(z);
    		}
    		else if (x == y->left && y == z->right)
    		{
    			right_rotate(y);
    			left_rotate(z);
    		}
    	}
    
    }
    Example of failure:
    Code:
    ***** start test 1: splay a chain *****
    (Note that this tree is backwards -- probably caused by my code. )
    8
        7
            6
                5
                    4
                        3
                            2
                                1
    **search 1:
        8
                7
            6
                    5
                4
                        3
                    2
    1
    **search 2:
        8
                    7
                6
                    5
            4
                3
    2
        1
    **search 3:
            8
                    7
                6
                    5
        4
    3
        2
            1
    **search 4:
        8
                7
            6
                5
    4
        3
            2
                1
    **search 5:
            8
                7
        6
    5
        4
            3
                2
                    1
    **search 6:
        8
            7
    6
        5
            4
                3
                    2
                        1
    **search 7:
        8
    7
        6
            5
                4
                    3
                        2
                            1
    **search 8:
    8
        7
            6
                5
                    4
                        3
                            2
                                1
    ***** end test 1 *****
    Every passing hour brings the Solar System forty-three thousand miles closer to Globular Cluster M13 in Hercules -- and still there are some misfits who insist that there is no such thing as progress.

  6. #6
    Kitten CornedBee's Avatar
    Join Date
    Aug 2001
    Location
    In a microchip!
    Posts
    11,594
    My advantage is that I pass references to references to my rotates, maybe you should pass references to pointers, too?


    In the C# CodeBank is a complete binary tree, maybe you can just rewrite it in C++, shouldn't be too hard.
    All the buzzt
    CornedBee

    "Writing specifications is like writing a novel. Writing code is like writing poetry."
    - Anonymous, published by Raymond Chen

    Don't PM me with your problems, I scan most of the forums daily. If you do PM me, I will not answer your question.

  7. #7

    Thread Starter
    PowerPoster sunburnt's Avatar
    Join Date
    Feb 2001
    Location
    Boulder, Colorado
    Posts
    1,403
    Actually, I think I got it working -- I made some code changes, but I also took a second look at the output it's giving: Apparently the top of the tree is the far left item, and the tree is sideways! Unfortunantly my instructor has written most of the code and left those three functions to fill in, with the instruction not to change any declarations.
    Every passing hour brings the Solar System forty-three thousand miles closer to Globular Cluster M13 in Hercules -- and still there are some misfits who insist that there is no such thing as progress.

  8. #8
    Kitten CornedBee's Avatar
    Join Date
    Aug 2001
    Location
    In a microchip!
    Posts
    11,594
    What's the learning effect there? Teamwork, how to code to accomodate your teammate's flawed code?
    All the buzzt
    CornedBee

    "Writing specifications is like writing a novel. Writing code is like writing poetry."
    - Anonymous, published by Raymond Chen

    Don't PM me with your problems, I scan most of the forums daily. If you do PM me, I will not answer your question.

  9. #9

    Thread Starter
    PowerPoster sunburnt's Avatar
    Join Date
    Feb 2001
    Location
    Boulder, Colorado
    Posts
    1,403
    I agree with you, but it's not my say

    I think the reason is to make it easy for the auto grading program to grade. I suspose I could turn in a different version as my hard copy.
    Every passing hour brings the Solar System forty-three thousand miles closer to Globular Cluster M13 in Hercules -- and still there are some misfits who insist that there is no such thing as progress.

  10. #10

    Thread Starter
    PowerPoster sunburnt's Avatar
    Join Date
    Feb 2001
    Location
    Boulder, Colorado
    Posts
    1,403

    Red Black Trees!

    Sorry to resurect this dead post, but the subject was rather related.

    This time, I'm doing red black trees!

    My instructor wrote the remove() function, and I am required to write the RB-Delete-Fixup function, which I have included here:

    Code:
    void RBTree::fixup(NodePointer x)
    {
    	while( x != root_ptr && is_black(x) )
    	{
    		if (x == x->p->left)
    		{
    			NodePointer w = x->p->right;
    
    			if (is_red(w))
    			{
    				make_black(w);
    				make_red(x->p);
    				left_rotate(x->p);
    				
    				w = x->p->right;
    
    			}
    			
    			if (w->left && w->right && is_black(w->left) && is_black(w->right))
    			{
    				make_red(w);
    				x = x->p;
    			}
    			else
    			{
    				if (is_black(w->right))
    				{
    					make_black(w->left);
    					make_red(w);
    
    					right_rotate(w);
    
    
    					w = x->p->right;
    				}
    				w->black = x->p->black;
    				make_black(x->p);
    				make_black(w->right);
    
    				left_rotate(x->p);
    
    				
    				x = root_ptr;
    			}
    		}
    		else // right child
    		{	
    			NodePointer w = x->p->left;
    
    			if (is_red(w))
    			{
    				make_black(w);	
    				make_red(x->p);
    				right_rotate(x->p);
    				
    
    				w = x->p->left;
    			}
    			
    			if (w->left && w->right && is_black(w->left) && is_black(w->right))
    			{
    				make_red(w);
    				x = x->p;
    			}
    			else
    			{
    				if (is_black(w->left))
    				{
    					make_black(w->right);
    					make_red(w);
    					left_rotate(w);
    
    					w = x->p->left;
    				}
    				w->black = x->p->black;
    				
    				make_black(x->p);
    				make_black(w->left);
    
    				right_rotate(x->p);
    				
    				x = root_ptr;
    			}
    		}
    	}
    }
    The problem is that remove() is calling fixup() with a NIL node* is this allowed - it's causing the is_black(w->child) call to try to evaluate a null pointer.

    Do you see any bugs here?
    Every passing hour brings the Solar System forty-three thousand miles closer to Globular Cluster M13 in Hercules -- and still there are some misfits who insist that there is no such thing as progress.

  11. #11
    Kitten CornedBee's Avatar
    Join Date
    Aug 2001
    Location
    In a microchip!
    Posts
    11,594
    Problem is, I've only learned the German names for these things. Can you quickly explain the features of a red-black tree to me?
    All the buzzt
    CornedBee

    "Writing specifications is like writing a novel. Writing code is like writing poetry."
    - Anonymous, published by Raymond Chen

    Don't PM me with your problems, I scan most of the forums daily. If you do PM me, I will not answer your question.

  12. #12

    Thread Starter
    PowerPoster sunburnt's Avatar
    Join Date
    Feb 2001
    Location
    Boulder, Colorado
    Posts
    1,403
    Each node has a color, red or black.
    The root node is always black.

    External nodes are nodes with no children and no key value. These are called NIL nodes. They are always black.

    Red Isolation Property: no red node has a red child.
    Black Height Property: every path from the root to a leaf (going only downward) has the same number of black nodes.

    These properties help keep the tree full.

    After deletion if we have deleted a black node, the tree must be fixed so that these properties still apply.

    Do you need more information? There is an overview here in pdf format.

    http://www.ulb.ac.be/di/rwuyts/DEAAl...ancedTrees.pdf
    Last edited by sunburnt; Feb 20th, 2004 at 02:33 PM.
    Every passing hour brings the Solar System forty-three thousand miles closer to Globular Cluster M13 in Hercules -- and still there are some misfits who insist that there is no such thing as progress.

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  



Click Here to Expand Forum to Full Width