left rotation in bst with 4 fields

Question

I have some problem with this and I tried a lot to solve it. I understand how rotation of bst work but I could not conform it to this structure.

Assume that the object Node of the binary search tree (BST) is described by 4 fields : key (integer), leftChild, rightChild and parent all are references to a Node of the BST. Write the code of leftRotation (Node p).

this is my trying code:

Node temp
temp = parent.right// could I do like this ??
parent.rightChild = temp.leftChild
temp.leftChild= parent

i feel it is totally wrong because I just wanna work with only those four fields. I just want a pseudo code.

thank you for help! regards

Answer 1

Assuming you don't know is p left child or right child of it's parent

q = p.right
if p.parent <> nil then
  if p.parent.right = p then
    p.parent.right = q  
  else
    p.parent.left = q  
q.parent = p.parent

q.left.parent = p
p.right = q.left

q.left = p
p.parent = q