# Thread: Left / Right rotate

1. ## 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.

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

3. 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>
{
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;
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;
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)

4. 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;
}```

5. 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 *****```

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

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

8. What's the learning effect there? Teamwork, how to code to accomodate your teammate's flawed code?

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

10. ## 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?

11. 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?

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

#### Posting Permissions

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

Featured