Binary Tree Rotation

trees

Definition

Binary Tree Rotation

Binary tree rotations are operations on a binary tree that changes the structure without interfering with the order of the elements.

Height

The height of an empty tree is defined as $-1$:

def height(u: TreeNode) -> int:
	if u == null:
		return -1
	else:
		return u.height

Types

Left Rotation

Algorithm:

def rotate_left(u: TreeNode) -> TreeNode:
    v = u.right
	
    u.right = v.left
    v.left = u 
	
    u.height = max(height(u.left), height(u.right)) + 1
    v.height = max(height(v.left), height(v.right)) + 1 
	
    return v

Right Rotation

Algorithm:

def rotate_right(u: TreeNode) -> TreeNode:
	v = u.left
	
	u.left = v.right
	v.right = u
	
	u.height = max(height(u.left), height(u.right)) + 1
	v.height = max(height(v.left), height(u)) + 1
	
	return v

Double Left-Right

def double_rotate_left_right(u: TreeNode) -> TreeNode:
	u.left = rotate_left(u.left)
	return rotate_right(u)

Double Right-Left

def double_rotate_right_left(u: TreeNode) -> TreeNode:
	u.right = rotate_right(u.right)
	return rotate_left(u)