AVL operations under the same ordered-set contract

After this page, you should be able to:

• Reuse the same ordered queries and public contracts with AVL update helpers.

• Separate logarithmic paths, rotation work, traversal output and metadata storage.

Builds on: AVL insertion, AVL deletion and Topic 7’s OrderedSet adapter.

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.

Purpose and operation contracts¶

AVL balancing changes how short the paths stay, not what a set operation means. Use the same operation table: add ignores duplicates; remove is strict and returns None; discard tolerates absence; inspections leave the tree unchanged; extraction removes and returns an extreme. Missing extremes or neighbours raise KeyError in that adapter.

The raw avl_insert and avl_delete helpers instead return the resulting subtree root. Missing-key raw deletion leaves the key set unchanged. Do not mistake this low-level policy for the public strict-remove policy, or a rotation’s root result for an inserted/deleted record.

Representation and all maintained invariants¶

• Strict BST ordering holds at every node, with one node per distinct key.

• Each cached height agrees with the actual child links: empty −1, leaf 0.

• Every node has balance factor between −1 and +1.

• The adapter’s total count equals the number of reachable nodes.

The first invariant makes ordinary BST queries correct; the next two bound path length; the last makes size/empty constant time. AVLNode stores no parent pointer, cached minimum or subtree counts for rank/select.

Trace the same operations through a different shape¶

Insert 30,10,20. The insertion reading’s LR repair yields root 20 with children 10 and 30. Repeating add(20) changes neither the keys nor the count. Successor(15) returns 20 without mutation. Extract-minimum returns 10; the remaining sorted keys are 20,30, regardless of any valid shape chosen by later repairs.

Python implementation and reuse¶

Read the Topic 7 query helpers and adapter, then Topic 8’s node/height, rotation, rebalance, insertion and deletion definitions in one session. The shared readers inspect only key, left and right; no separate AVL search algorithm is required.

balanced = OrderedSet(avl_insert, avl_delete)
for key in [30, 10, 20]:
    balanced.add(key)
balanced.add(20)
assert balanced.size() == 3
assert balanced.keys() == [10, 20, 30]
assert balanced.successor(15) == 20
assert balanced.range_keys(15, 30) == [20, 30]
assert balanced.extract_min() == 10
assert balanced.keys() == [20, 30]

var balanced = new OrderedSet(avl_insert, avl_delete);
for (const key of [30, 10, 20]) balanced.add(key);
balanced.add(20);
console.assert(balanced.size() === 3);
console.assert(JSON.stringify(balanced.keys()) === "[10,20,30]");
console.assert(balanced.successor(15) === 20);
console.assert(JSON.stringify(balanced.range_keys(15, 30)) === "[20,30]");
console.assert(balanced.extract_min() === 10);
console.assert(JSON.stringify(balanced.keys()) === "[20,30]");

balanced = OrderedSet(avl_insert, avl_delete)
for key in [30, 10, 20]; add!(balanced, key); end
add!(balanced, 20)
@assert length(balanced) == 3
@assert ordered_keys(balanced) == [10, 20, 30]
@assert successor(balanced, 15) == 20
@assert range_keys(balanced, 15, 30) == [20, 30]
@assert extract_min!(balanced) == 10
@assert ordered_keys(balanced) == [20, 30]

Implementation choices and correctness¶

The adapter always reconnects the updated root, including after rotations. Only the AVL insert/delete pair may mutate this AVL-backed instance; calling ordinary bst_insert on its nodes could introduce nodes without height metadata and bypass balancing. Read-only BST queries are safe to reuse because AVL ordering is the same.

Using cached heights makes each local check constant work. Recomputing whole-subtree heights at every ancestor would change the update cost. A manual rotation preserves key order when its structural precondition holds, but it need not restore balance unless chosen by the repair algorithm.

Time and space costs¶

Let L=log₂(n+2), so even an empty-tree operation has a constant bound.

Persistent storage is O(n+1), including one height per node and the adapter’s total count. Rotations use O(1) extra local storage. One insertion needs at most one single/double repair at the lowest unbalanced ancestor, though this code still returns through all ancestors. Deletion may repair several levels and still stays logarithmic. Traversal and reporting all keys cannot be logarithmic because the output itself has n items.

When to use it¶

AVL trees suit changing ordered data when worst-case path bounds matter. They require more update bookkeeping than an ordinary BST. For one static collection, compare sorted-array search and its preparation costs; for exact-key membership alone, compare a hash set’s qualified expected bounds. The common contract allows behaviour to be compared separately from these trade-offs.

Check your understanding¶

1. Can the iterative BST successor helper be used on AVL nodes without computing balance factors?

2. Is a sorted inorder list enough to validate an AVL update?

Continue in sidebar order to spatial search, which changes the partition invariant. For the graph route, you can instead go directly to priority queues and heaps, or return to balanced search trees.