Balanced search tree

Key order determines search direction but does not automatically keep paths short. Monotonically inserted keys can turn an ordinary BST into a chain. A balancing policy checks additional properties after updates to prevent uncontrolled skew.

Balance need not put every binary-tree leaf at the same depth. AVL trees limit subtree-height differences, while red-black trees constrain paths through colors and black height. Different invariants can produce logarithmic height without perfect binary symmetry.

References: [1] [2] [3]

A rotation changes local parent–child links while preserving inorder key order. A child moves to the local root, the former root moves down, and the intermediate key range is reattached appropriately. Shape changes without changing the ordering relation.

Each policy also maintains its metadata. AVL trees update heights; red-black implementations can rotate and recolor; multi-key trees split or merge nodes. Link changes without the required bookkeeping do not preserve the promised balancing properties.

References: [2] [4]

Controlled height supports logarithmic worst-case search and updates while retaining ordered operations such as minima, maxima, and ranges. The benefit includes the query capabilities supplied by an ordered structure, beyond one exact-key lookup.

Policies differ in metadata, repair steps, and implementation complexity. Selection depends on required operations, update patterns, and resources. Balancing does not define business-level equality: the comparison relation still has to represent the intended key order.

References: [2] [3]