-
Jan 22nd, 2004, 05:11 PM
#1
Thread Starter
PowerPoster
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.
-
Jan 23rd, 2004, 04:48 AM
#2
transcendental analytic
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.
-
Jan 23rd, 2004, 06:48 AM
#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>
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.
-
Jan 23rd, 2004, 06:50 AM
#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;
}
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.
-
Jan 27th, 2004, 09:39 PM
#5
Thread Starter
PowerPoster
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.
-
Jan 28th, 2004, 05:29 AM
#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.
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.
-
Jan 28th, 2004, 01:00 PM
#7
Thread Starter
PowerPoster
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.
-
Jan 29th, 2004, 12:44 PM
#8
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.
-
Jan 29th, 2004, 11:47 PM
#9
Thread Starter
PowerPoster
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.
-
Feb 19th, 2004, 09:07 PM
#10
Thread Starter
PowerPoster
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.
-
Feb 20th, 2004, 05:22 AM
#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?
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.
-
Feb 20th, 2004, 02:20 PM
#12
Thread Starter
PowerPoster
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
-
Forum Rules
|
Click Here to Expand Forum to Full Width
|