Rotation

Single and double rotations restore balance.

Rotation

When the balance breaks in AVL a rotation is done. Right rotation: in a left-heavy case, brings the left child up.

In a right rotation: y = x.left, x.left = y.right, y.right = x. Now y is the new root, x its right child.

The rotation preserves the BST property and reduces height. It is O(1).

Four cases

AVL has four imbalance cases: left-left (right rotate), left-right (left then right rotate), right-right (left rotate), right-left (right then left rotate).

Left-right and right-left need double rotation: first a sub-rotation, then the main one. This fixes complex skews.

In every case the result: balance factor returns to -1,0,+1; the BST property is preserved.

Exercise Right rotation

Write rotate_right(x). y = x.left, x.left = y.right, y.right = x, return y. Print 2 3 with root = Node(3); root.left = Node(2); root.left.left = Node(1); new_root = rotate_right(root); print(new_root.val, new_root.right.val).

Show example solution

class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None
def rotate_right(x):
    # Right rotation
    y = x.left
    x.left = y.right
    y.right = x
    return y
root = Node(3)
root.left = Node(2)
root.left.left = Node(1)
new_root = rotate_right(root)
print(new_root.val, new_root.right.val)

Test yourself

Right rotation

y = x.left
x.left = y.____
y.right = x

Show answer

y = x.left
x.left = y.right
y.right = x

Rotation: match the terms

Left-left

Right rotate
Right-right

Left rotate
Left-right

Left first
Right-left

Right first
Which case does right rotation fix?
- Right-right
- Left-right
- Left-left
- Right-left
Show answer

Left-left — Left-left

Next lesson: Balance after insert

We Are Enhancing Your Experience

Cookie Preferences

Strictly Necessary Cookies

Analytical Cookies