Choose the claim that matches each structure's actual guarantee. Distinguish expected cost from a strict worst-case bound and in-memory versions from durable records.
Lessons
- Bloom filters: reject absent keys without claiming exact membership
- Sparse sets: constant-time membership for bounded integer IDs
- Skip lists: randomized levels over an ordered bottom chain
- B+ leaf pages: split full pages and keep range order
- Persistent segment trees: retain old range-sum versions
- Monotonic deques: maintain a sliding minimum in linear time