Balance after insert
- Algorithms course
- Intermediate
- Lesson 35/80
- 4 min
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).
Practice 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).
Starter code
def rotate_left(x):
# Left rotationSample 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)Expected output
2 1
Questions and answers
Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.
1 Balance after insert: match the terms
| Term | Meaning |
|---|---|
Insert |
O(log n) |
Balance check |
Upward path |
|bf| > 1 |
Rotate |
Result |
Balanced |
2 What does left rotation fix?
- Left-heavy
- Empty tree
- Balanced
- Right-heavy Correct answer
Explanation: Right-heavy
3 Left rotation
y = x.right
x.right = y.____
y.left = xy = x.right
x.right = y.left
y.left = xExplanation: left is right.