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
graph TD
x((x)) --> alpha((α))
x --> y((y))
y --> beta((β))
y --> gamma((γ))
graph TD
y((y)) --> x((x))
y --> gamma((γ))
x --> alpha((α))
x --> beta((β))
graph TD
y((y)) --> x((x))
y --> gamma((γ))
x --> alpha((α))
x --> beta((β))
graph TD
x((x)) --> alpha((α))
x --> y((y))
y --> beta((β))
y --> gamma((γ))
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