BST key order. Child heights identify one of four imbalance shapes; rotations preserve inorder key order while reducing height.

A rotation changes who is parent, not the sorted order seen by inorder traversal. The height summary says where the tree bent too far; one or two local rotations straighten it.

What the function promises: Insert distinct comparable keys and return an AVL root. Duplicate insertions keep the existing node; deletion is outside this example.

class AVLNode:
    def __init__(self, key):
        self.key, self.left, self.right, self.height = key, None, None, 1

def height(node): return node.height if node else 0

def refresh(node):
    node.height = 1 + max(height(node.left), height(node.right))

def rotate_left(root):
    top, middle = root.right, root.right.left
    top.left, root.right = root, middle
    refresh(root); refresh(top)
    return top

def rotate_right(root):
    top, middle = root.left, root.left.right
    top.right, root.left = root, middle
    refresh(root); refresh(top)
    return top

def avl_insert(root, key):
    if root is None: return AVLNode(key)
    if key < root.key: root.left = avl_insert(root.left, key)
    elif key > root.key: root.right = avl_insert(root.right, key)
    else: return root
    refresh(root)
    balance = height(root.left)-height(root.right)
    if balance > 1:
        if key > root.left.key: root.left = rotate_left(root.left)
        return rotate_right(root)
    if balance < -1:
        if key < root.right.key: root.right = rotate_right(root.right)
        return rotate_left(root)
    return root

root = None
for key in [1,2,3,4,5]: root = avl_insert(root, key)
assert root.key == 2 and root.height == 3
assert root.left.key == 1 and root.right.key == 4

Work and storage: O(log n) insertion and search when the invariant holds; O(n) nodes and O(log n) recursion depth.

When to recognize it: Child heights identify one of four imbalance shapes; rotations preserve inorder key order while reducing height.

Check before applying it: Every mutation must refresh heights in the correct order; production ordered maps also need deletion and concurrency policies.

B-trees use many keys per node to reduce expensive page reads; binary rotations are tuned for memory-resident pointer trees.