Balance after insert

Rebalance after an insert.

Balance after insert

After inserting into an AVL, we climb from the inserted node to the root checking each node's balance factor. If |bf| > 1 a rotation is done at that node.

After rotation the subtree's height returns to its old value; so no imbalance occurs higher up. This is the key to AVL's efficiency.

Insertion is O(log n): the insertion path + balance check are both log n.

Left rotation

Left rotation fixes the right-heavy case. y = x.right, x.right = y.left, y.left = x, return y.

Now y is the new root, x its left child. The BST property is preserved, height decreases.

In the right-left case a right rotation is done first, then a left rotation (double rotation).

Exercise Left rotation

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

Show example solution

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

Test yourself

Balance after insert: match the terms

Insert

O(log n)
Balance check

Upward path
|bf| > 1

Rotate
Result

Balanced
What does left rotation fix?
- Left-heavy
- Empty tree
- Balanced
- Right-heavy
Show answer

Right-heavy — Right-heavy

Left rotation

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

Show answer

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

Next lesson: Summary - AVL tree

We Are Enhancing Your Experience

Cookie Preferences

Strictly Necessary Cookies

Analytical Cookies