AVL and red-black: preserving balance

AVL keeps each node's left/right height difference within1. Update affected ancestors after insertion, using single LL/RR or double LR/RL rotations. Rotations preserve inorder key order while changing shape. Deletion may require balancing at several ancestors.

Red-black trees bound height using colour rules: black root, no red-red parent-child pair, and equal black height to NIL leaves. These support height≤2log₂(n+1). NIL represents mathematical missing-child leaves, implemented through sentinels or null handling.

AVL has stricter balance; red-black has different update constants. Neither is universally faster. Educational implementations must maintain parent/root links and augmented metadata, while production use should usually rely on tested libraries.

# Right rotation in tuple form: (key, left, right).
def rotate_right(y):
    ykey, x, right = y
    if x is None: raise ValueError("missing pivot")
    xkey, left, middle = x
    return (xkey, left, (ykey, middle, right))
assert rotate_right((30,(20,(10,None,None),None),None))[0] == 20