LL, RR, LR and RL cases

After this page, you should be able to:

• Identify straight and bent imbalance patterns from child factors.

• Choose repairs that also handle deletion’s zero-factor child.

Builds on: Rotations preserve key order and transferred subtrees.

Code languages: Python defines the explanations, figures and self-checks. Use the language guide for native conventions and dependencies. Complete runnable topic examples: Python · JavaScript · Julia.

The same BST readers and OrderedSet interface are reused from Topic 7. Julia updates use function calls, not dot methods. All variants use empty height −1, leaf height 0, and left height minus right height; rotations must return and reconnect the new subtree root.

Repair contract¶

rebalance(node) takes a nonempty node whose child subtrees are already valid AVL trees with correct heights. After one valid single-key update, it refreshes this node and returns the repaired subtree root with the same keys. Its caller must reconnect the result. It is not a validator or repair routine for arbitrarily corrupted trees.

Name the heavy path from the unbalanced node¶

Let z be the ancestor being repaired. The first letter describes its heavy child; the second describes the heavy direction within that child. The names describe the shape causing imbalance, not the direction of the corrective rotation.

Straighten an inner bend before promoting it¶

In LR, node 20 is too deep in the left child’s right branch. First rotate that child left, converting the local shape to LL. Then rotate the old root right. RL is the mirror image.

A single rotation in the original LR shape may preserve sorted order but fail to establish AVL balance. Order preservation and balance repair are different obligations; a correct repair must do both. Larger examples retain the middle and outside subtrees exactly as described on the rotation page.

Choose the repair from child balance factors¶

def rebalance(node):
    update_height(node)
    bf = balance_factor(node)
    if bf > 1:
        if balance_factor(node.left) < 0:
            node.left = rotate_left(node.left)
        return rotate_right(node)
    if bf < -1:
        if balance_factor(node.right) > 0:
            node.right = rotate_right(node.right)
        return rotate_left(node)
    return node

function rebalance(node) {
    update_height(node); const bf = balance_factor(node);
    if (bf > 1) {
        if (balance_factor(node.left) < 0) node.left = rotate_left(node.left);
        return rotate_right(node);
    }
    if (bf < -1) {
        if (balance_factor(node.right) > 0) node.right = rotate_right(node.right);
        return rotate_left(node);
    }
    return node;
}

function rebalance(node)
    update_height!(node); bf = balance_factor(node)
    if bf > 1
        balance_factor(node.left) < 0 && (node.left = rotate_left(node.left))
        return rotate_right(node)
    elseif bf < -1
        balance_factor(node.right) > 0 && (node.right = rotate_right(node.right))
        return rotate_left(node)
    end
    return node
end

This helper requires a nonempty node whose child subtrees are already AVL-valid with correct heights. The current node may need repair after a single-key update. Bottom-up recursion establishes that precondition at each level.

The strict < 0 and > 0 inner tests matter for deletion: a heavy child with factor zero uses a single rotation. Insertion-only rules based on the newly inserted key cannot simply be reused for deletion, where no inserted key identifies a path.

Implementation choices and local costs¶

Child-factor tests handle both insertion and deletion, including a zero-factor heavy child. Each call does O(1) work and at most two rotations with O(1) local workspace. This does not include reaching the node or checking the full update path. Choosing cases by a newly inserted key is an insertion-specific alternative; it cannot stand in for the shared deletion-capable helper.

Check your understanding¶

Predict the returned result, links or invariant before opening the explanation.

1. BF(z)=+2 and BF(z.left)=−1. Where does the first returned root reconnect?

2. If the heavy child has factor zero after deletion, must repair be double?

Next: Insertion.