DSA Rotations and AVL Balance
A rotation is a local rearrangement that swaps a parent with one child while keeping the inorder sequence unchanged. An AVL tree is a BST that rotates after inserts to keep every height difference within one.
The left-left case and a right rotation
Values 30, 20 and 10 lean left in a chain, so the balance factor of 30 is 2. One right rotation lifts 20 to the root, and the balance becomes 0.
class TreeNode:
def __init__(self, value, left=None, right=None):
self.value = value
self.left = left
self.right = right
def shape(node):
if node is None:
return None
return (node.value, shape(node.left), shape(node.right))
def height(node):
if node is None:
return -1
return 1 + max(height(node.left), height(node.right))
def balance(node):
return height(node.left) - height(node.right)
def rotate_right(y):
x = y.left
middle = x.right
x.right = y
y.left = middle
return x
def rotate_left(x):
y = x.right
middle = y.left
y.left = x
x.right = middle
return y
root = TreeNode(30, TreeNode(20, TreeNode(10)))
print("before:", shape(root))
print("balance of 30:", balance(root))
root = rotate_right(root)
print("after right rotation:", shape(root))
print("balance of 20:", balance(root))The right-right case and a left rotation
Values 10, 20 and 30 lean right in a chain, so the balance factor of 10 is minus 2. One left rotation lifts 20 to the root, and the balance becomes 0.
class TreeNode:
def __init__(self, value, left=None, right=None):
self.value = value
self.left = left
self.right = right
def shape(node):
if node is None:
return None
return (node.value, shape(node.left), shape(node.right))
def height(node):
if node is None:
return -1
return 1 + max(height(node.left), height(node.right))
def balance(node):
return height(node.left) - height(node.right)
def rotate_right(y):
x = y.left
middle = x.right
x.right = y
y.left = middle
return x
def rotate_left(x):
y = x.right
middle = y.left
y.left = x
x.right = middle
return y
root = TreeNode(10, None, TreeNode(20, None, TreeNode(30)))
print("before:", shape(root))
print("balance of 10:", balance(root))
root = rotate_left(root)
print("after left rotation:", shape(root))
print("balance of 20:", balance(root))The left-right case needs two rotations
The heavy path bends at 10, so one rotation cannot straighten it. Rotating the child first makes the chain straight, and the root rotation then finishes the repair.
class TreeNode:
def __init__(self, value, left=None, right=None):
self.value = value
self.left = left
self.right = right
def shape(node):
if node is None:
return None
return (node.value, shape(node.left), shape(node.right))
def height(node):
if node is None:
return -1
return 1 + max(height(node.left), height(node.right))
def balance(node):
return height(node.left) - height(node.right)
def rotate_right(y):
x = y.left
middle = x.right
x.right = y
y.left = middle
return x
def rotate_left(x):
y = x.right
middle = y.left
y.left = x
x.right = middle
return y
root = TreeNode(30, TreeNode(10, None, TreeNode(20)))
print("before:", shape(root))
root.left = rotate_left(root.left)
print("after rotating the child:", shape(root))
root = rotate_right(root)
print("after rotating the root:", shape(root))
print("balance of 20:", balance(root))Example
class TreeNode:
def __init__(self, value, left=None, right=None):
self.value = value
self.left = left
self.right = right
def shape(node):
if node is None:
return None
return (node.value, shape(node.left), shape(node.right))
def height(node):
if node is None:
return -1
return 1 + max(height(node.left), height(node.right))
def balance(node):
return height(node.left) - height(node.right)
def rotate_right(y):
x = y.left
middle = x.right
x.right = y
y.left = middle
return x
def rotate_left(x):
y = x.right
middle = y.left
y.left = x
x.right = middle
return y
def fix(node):
if balance(node) > 1:
if balance(node.left) < 0:
node.left = rotate_left(node.left)
return rotate_right(node)
if balance(node) < -1:
if balance(node.right) > 0:
node.right = rotate_right(node.right)
return rotate_left(node)
return node
cases = [
("left-left", TreeNode(30, TreeNode(20, TreeNode(10)))),
("right-right", TreeNode(10, None, TreeNode(20, None, TreeNode(30)))),
("left-right", TreeNode(30, TreeNode(10, None, TreeNode(20)))),
("right-left", TreeNode(10, None, TreeNode(30, TreeNode(20)))),
]
for name, root in cases:
print(name, "before:", shape(root), "root balance:", balance(root))
root = fix(root)
print(name, "after:", shape(root), "root balance:", balance(root))Key points
- The balance factor of a node is its left subtree height minus its right subtree height
- AVL keeps every balance factor between minus one and one
- A right rotation lifts the left child into the parent's place
- A left rotation is the mirror move, lifting the right child
- The four cases are named by the heavy path: left-left, right-right, left-right and right-left
- The bent cases need a rotation on the child before the rotation on the node
- A red-black tree colours each node red or black and forbids two red nodes in a row on any path
In this example, all four rotation cases are repaired in turn by one fix function. Each before shape leans on one side with a root balance of 2 or minus 2. Each after shape is the same balanced tree with root 20 and balance 0. The bent cases pass through the same function, which rotates the heavy child first.
Note
this lesson implements AVL rotations in code and surveys red-black trees as rules only.
Try it Yourself
Edit the code, then press Run.
Running is simulated · Python Playground
Exercise
A node has left subtree height 4 and right subtree height 2. What is its balance factor, and what does AVL require?