AVL tree

An AVL tree preserves ordinary BST key order and additionally requires the heights of both child subtrees to differ by at most one at every node. Checking only the root’s apparent symmetry is insufficient.

One convention defines the balance factor as left height minus right height, allowing −1, 0, or 1. Stored heights must be recomputed from children so that updates can identify which ancestors require repair.

References: [1] [2]

When one side grows too tall, rotations promote a suitable child while preserving key order. The child’s own imbalance determines whether one rotation suffices or a preliminary child rotation is needed before rotating the original root.

The reference implementation updates size and height while returning through insertion and deletion, then rebalances. Its repaired local root is reconnected to the parent. Moving nodes without correcting metadata would leave subsequent height or count operations unsupported.

References: [2]

The height constraint gives logarithmic worst-case search, insertion, deletion, extrema, and boundary queries. This differs from favorable average analysis of a randomly built ordinary BST: the guarantee comes from a maintained invariant.

Princeton AVLTreeST compares keys through compareTo rather than equals or hashCode, replacing the associated value for an equal key. Balancing and the interface’s equality convention are distinct rules, both of which matter when selecting an ordered representation.

References: [1]