Ordering is useful because it supplies evidence about where a target cannot be. Binary search excludes part of a sorted sequence; a binary search tree excludes an entire subtree. The same reasoning leads to different storage and update costs.
Reading route¶
Binary search: maintain a candidate interval and make progress at every mismatch.
Search boundaries: find first/last duplicate boundaries and insertion positions.
Trees and the BST invariant: connect terminology to whole-subtree bounds.
BST lookup and insertion: follow one path and reconnect returned roots.
Traversal and ordered operations: recover sorted order, minimum and successor.
BST range queries: report a bounded key range while pruning irrelevant subtrees.
BST deletion: trace leaf, one-child and two-child removal without losing subtrees.
One ordered-set contract: public operations, strict/tolerant removal and extraction.
Search costs and choices: distinguish logarithmic search from the conditions that make it possible.
Review sorting, linked structures and recursive calls. Code stores one node per distinct key. Repeated insertion leaves the set unchanged; comparisons must define a consistent order.
The figures reuse the lecture tree rooted at 50. Topic 8 explains how to keep its paths short; Topic 9 changes the ordering rule for multidimensional points.
Consistent contracts and implementation scope¶
Read purpose/contract → invariant and representation → trace → code → choices/correctness → costs → suitability → self-checks. Exact binary search and boundary search return positions; BST readers return nodes or key snapshots; update helpers return subtree roots. The ordered-set adapter makes the public operation results explicit rather than confusing those different layers.
The seven-node reference tree precedes insertion of 65; pages explicitly identify examples that include it. Trace updates against the indicated starting tree rather than carrying a changed tree into the next independent example. The strict distinct-key policy applies to both BST and AVL implementations.
The supplied code covers exact/boundary array search, all three traversals, extremes, strict neighbours, closed ranges, BST updates and a shared public set interface. It does not implement a key–value ordered map, rank/select augmentation or a static median builder.
Code listings offer Python, JavaScript and Julia tabs where a runnable example is present. Python remains the explanation and trace language; see the language guide for native conventions and runnable topic downloads.