Open Addressing: All elements stored in the hash table itself. When a collision occurs, probe for another slot.

Linear Probing: $h(k, i) = (h'(k) + i) \pmod m$. Can lead to primary clustering.
Quadratic Probing: $h(k, i) = (h'(k) + c_1 i + c_2 i^2) \pmod m$. Can lead to secondary clustering.
Double Hashing: $h(k, i) = (h_1(k) + i h_2(k)) \pmod m$. Best results generally.

Left child $\le$ parent $\le$ right child.
Operations (Search, Min, Max, Successor, Predecessor, Insert, Delete): $O(h)$ where $h$ is tree height.
Worst-case height: $O(n)$ (skewed tree).
Average-case height: $O(\log n)$.

Self-balancing BST. Properties:

Every node is either red or black.
Root is black.
Every leaf (NIL) is black.
If a node is red, both its children are black.
All simple paths from a node to any descendant leaf contain the same number of black nodes (black-height).

Self-balancing search tree, optimized for disk access. Each node can have many children.

Degree $t \ge 2$:
- Every node has at most $2t-1$ keys.
- Every internal node has at most $2t$ children.
- Every node (except root) has at least $t-1$ keys and $t$ children.
- Root has at least 1 key (if not a leaf).
- All leaves have the same depth.
Height: $O(\log_t n)$.
Operations (Search, Insert, Delete): $O(t \log_t n)$ in terms of CPU time; $O(\log_t n)$ disk access.

Collection of min-heap-ordered trees. Amortized analysis.

Adjacency List: Array of lists. $O(V+E)$ space. Good for sparse graphs.
Adjacency Matrix: $V \times V$ matrix. $O(V^2)$ space. Good for dense graphs.

A spanning tree with minimum total edge weight.