COMP5112 Chap.6 Binary Search Trees and AVL Balance
Binary Search Trees and AVL Balance
Ordering converts comparisons into paths
A binary search tree requires every left-subtree key and every right-subtree key to respect bounds inherited from all ancestors. Operations take time proportional to height, so ordinary trees can degrade to linear chains while AVL trees use rotations to maintain logarithmic height.
The chapter covers search, insertion, minimum, deletion cases, global validity checks and the four imbalance patterns.
Search begins at the root. Equality succeeds, a smaller target follows the left reference, and a larger target follows the right. A failed search ends only when the comparison-selected child is absent; that location is also where insertion would attach a new leaf. Record every comparison and direction.
The route length is bounded by height h, so the honest general complexity is O of h before any balance assumption is introduced.
Insertion order determines ordinary tree shape. The same key set can form a compact tree or a one-sided chain. Sorted insertion is a useful stress test because each new key may become the right child of the previous one, producing linear height and linear search.
Inorder traversal remains sorted in both shapes, so correct ordering does not imply efficient height. Shape and key invariant are separate properties.
Validation must carry ancestor bounds. Checking only that each left child is smaller and each right child larger can miss a deep key that violates the root. Descending left tightens an upper bound; descending right tightens a lower bound.
A duplicate policy must say whether equal keys are rejected, stored as counts, or consistently placed on one side. Search, insertion and validation must use the same rule.
Deletion splits into structural cases. A leaf can be removed, and a one-child node can be bypassed.
A two-child node is replaced by its inorder successor or predecessor, then that boundary node is removed from its original location, where it has at most one child. Reconnect parents and endpoints carefully, preserve global key order, and continue checking stored heights when the representation is balanced.
An AVL tree restricts the height difference between left and right subtrees at every node.
After an update, find the lowest unbalanced ancestor and follow the heavy path. Left-left and right-right patterns use one rotation; left-right and right-left bends use two. Rotations change ancestry while preserving inorder order. Label outside subtrees before moving references, then verify their sorted intervals and recompute heights from the lower node upward.
Balancing trades update work for a height guarantee.
Ordinary trees may be simpler and fast for favourable insertion sequences, but they offer no logarithmic worst-case promise. AVL maintenance keeps height logarithmic, yielding predictable search, insertion and deletion bounds. For every complexity statement, write O of h first and substitute O of log n only after naming the balance guarantee that constrains h.
What this chapter covers
- 01
Global search-tree ordering
- 02
Search and insertion paths
- 03
Minimum and maximum
- 04
Leaf and one-child deletion
- 05
Two-child successor deletion
- 06
AVL balance and rotations
Worked example · free
Build a search tree from insertion order
- 3Place each key by comparisons.
- 2Trace the search path.
- 3Relate path length to height.
Key terms
- Search-Tree Property
- The global ordering of all keys in left and right subtrees.
- Successor
- The next key in sorted order, often used for two-child deletion.
- Balance Factor
- The difference between left and right subtree heights.
- Rotation
- A local restructuring that preserves inorder order while changing height.
Binary Search Trees and AVL Balance FAQ
Why is checking each parent and child not enough?
A deep descendant can be correctly ordered relative to its parent and still violate a bound inherited from an ancestor. Carry lower and upper bounds down the tree throughout validation.
Why does insertion order matter?
It selects the root and every later path. Sorted insertion into an ordinary tree can create a chain even though the same key set admits a balanced shape with shorter searches.
How do I choose an AVL rotation?
Find the lowest unbalanced ancestor and follow the heavy child path. Straight left-left or right-right paths use one rotation; bent paths use two while preserving inorder key order.
Exam move
Practise one search, insertion and deletion on the same tree, then write its inorder sequence and balance factors. Use those as independent checks of order and shape. Build the same key set under sorted and alternating insertion orders to expose height dependence. For rotations, label the four outside subtrees, perform the pointer change, regenerate inorder order and recompute heights bottom-up.
Always state O of h before deciding whether a balance guarantee permits substitution of logarithmic height.
Working through Binary Search Trees and AVL Balance in COMP5112? Sia is AskSia’s AI Computer Science tutor — ask any COMP5112 Binary Search Trees and AVL Balance question and get a clear, step-by-step explanation grounded in how COMP5112 is taught and assessed. Read this chapter free, then take your hardest questions to Sia.
