I'm working on a splay tree implementation for my Algorithms class. We were given the following psuedo code for a Left rotation:
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
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 -- Although I really didn't study it.) 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.