Binary Search Tree Rotations

What is it ?

It is an operation through which the pointer structure of a binary tree is altered, while preserving the binary-search tree properties. There are two rotations

x
α
y
β
γ
y
x
γ
α
β
y
x
γ
α
β
x
α
y
β
γ

How to do Left Rotation ?

    x.right = y.left # left element of y becomes right element of x
    if y.left is not None: # make x the parent of the left element
        y.left.parent = x
    y.parent = x.parent # make x's parent y's parent
    if x.parent is None: # if x's parent is none, then x was the root node.
        root = y # make y the root node in that case
    elif x == x.parent.left: # if x was left element of it's parent node
        x.parent.left = y # then make y the left element
    else:
        x.parent.right = y # else make y the right element
    y.left = x # make x, the left element of y
    x.parent = y # make y the parent of x

How to do Right Rotation

    y.left = x.right
    if x.right is not None:
        x.right.parent = y
    x.parent = y.parent
    if y.parent is None:
        root = x
    elif y == y.parent.left:
        y.parent.left = x
    else:
        y.parent.right = x
    x.right = y
    y.parent = x