Overview

Topic 2 closed with a genuine gap: hash tables give expected $O(1)$ lookup but destroy order (no "give me the next key above this one" query), while a plain sorted array gives ordered traversal but $O(n)$ insertion. This topic closes that gap with binary search trees (BSTs), which give $O(h)$ search, insertion, and ordered traversal simultaneously, where $h$ is the tree's height — then immediately confronts the fact that an adversarially- or unluckily-ordered sequence of insertions can make $h = \Theta(n)$, degrading a BST to a linked list. Red-black trees fix this by maintaining a balance invariant via rotations, guaranteeing $h = O(\log n)$ always. The topic closes with augmentation — the general recipe for extending a balanced tree with extra bookkeeping (rank, interval overlap) without breaking its balance guarantee — and a practical note on when Python's built-in heapq/bisect/dict/set suffice in place of hand-rolled trees.