Code with explanation for binary tree rotation (left OR right)

Question

I have been trying to wrap my brain around how to write code for rotation of binary tree. I looked at http://en.wikipedia.org/wiki/Tree_rotation and enfuzzled.com I have been staring at this for 2 hours and have looked at it multiple times earlier. I still see problems in the wikipedia article and cannot understand the other one completely e.g.

Both these lines mentioned in the wikipedia article cannot be true at once

Let P be Q's left child. Set P to be the new root.

Can anyone please help?Thanks

Gotcher

That article is a kind of formal description. Articles about actual balanced tree rotation is more easy to read, such as this: en.wikipedia.org/wiki/Red-black_tree – Venipuncture

Thanks. That article also does not have code for rotation. I am finding it very hard to find code. I have scanned a lot of courses available on web and every where (as in my alma mater) teaches the concepts but not the code. The code for this can be pretty tricky and after multiple iterations, I am looking for some guidance – Gotcher

Answer 1

According to your comments to the question you are looking for the guidance for the rotation algorithm. Here is LEFT-ROTATE algorithm from an excellent book http://www.amazon.com/Introduction-Algorithms-Third-Thomas-Cormen/dp/0262033844.

Cyclopean

Answer 2

"Let P be Q's left child. Set P to be the new root." Basically that's the description of the rotation to the right or clockwise:

  Q      P
 /   =>   \
P          Q

Cyclopean

Oops. Thanks. I stared at this again and now I understand. So the first statement Let P be Q's left child is an attempt to fix the symbol in the original tree. I keep on thinking that P is Q's left child in the new tree. I am sorry, I am really dumb.Thanks again – Gotcher

Nothing for. BTW, dumb people don't really realize the are dumb :) – Cyclopean

Answer 3

Here's the LEFT-ROTATE in my edition of the Corman book

Geraldina

Answer 4

This answer is from https://www.codesdope.com/course/data-structures-red-black-trees-insertion/ All credit to those guys.

LEFT_ROTATION(T, x) y = x.right x.right = y.left

The left child of y is going to be the right child of x - x.right = y.left. We also need to change the parent of y.left to x. We will do this if the left child of y is not NULL.

if y.left != NULL y.left.parent = x

Then we need to put y to the position of x. We will first change the parent of y to the parent of x - y.parent = x.parent. After this, we will make the node x the child of y's parent instead of y. We will do so by checking if y is the right or left child of its parent. We will also check if y is the root of the tree.

y.parent = x.parent
if x.parent == NULL //x is root
  T.root = y
elseif x == x.parent.left // x is left child
  x.parent.left = y
else // x is right child
  x.parent.right = y

At last, we need to make x the left child of y.

y.left = x
x.parent = y

LEFT_ROTATE(T, x)
  y = x.right
  x.right = y.left
  if y.left != NULL
      y.left.parent = x
  y.parent = x.parent
  if x.parent == NULL //x is root
      T.root = y
  elseif x == x.parent.left // x is left child
      x.parent.left = y
  else // x is right child
      x.parent.right = y
  y.left = x
  x.parent = y

Cue