Hashing maps a key to a short fixed-length hash code indexing a slot. A collision is two keys to one slot. Chaining: linked list per slot; load factor a=n/m; Theta(1+a) avg, Theta(n) worst. Open addressing: probe for a free slot, a<=1; linear probing h(k,i)=(h'(k)+i) mod m (primary clustering); quadratic; double hashing h(k,i)=(h1(k)+i.h2(k)) mod m.
Good function: determined by data, uses all input, uniform, differs for similar strings. Division (k mod m, m prime), multiplication, mid-square, folding. Universal hashing: family H where two distinct keys collide with probability <= 1/m. Rehashing: table nearly full -> double it, re-insert all keys.
Left subtree keys <= node, right >= node. In-order (L,root,R) gives sorted order Theta(n); pre-order (root,L,R); post-order (L,R,root).
Search O(h); min = leftmost, max = rightmost; successor = leftmost of right subtree (else lowest ancestor); insert as a leaf O(h); delete: 0/1 child remove/replace, 2 children replace by successor. All O(h).
Root black; NIL leaves black; no red-red; equal black-height on every path -> height O(log n). Rotations restructure preserving BST order. RB-INSERT colours the node red then RB-INSERT-FIXUP (3 cases); RB-DELETE-FIXUP has 4 cases. Both O(log n).