A dynamic set stores indexed elements while supporting insertions and removals. When the elements must remain sorted, the main operations are fast search, insertion, and removal rather than one-time lookup. section 3.4.3 section 6.1.1
Choose the structure according to whether the set is static, mutable, ordered, or sensitive to worst-case behavior:
- Use a tree for an open dynamic set when search, insert, and remove must all remain available; a balanced tree takes O(log n) node traversals per operation. section 6.1.1
- Prefer a hash table or Bloom filter for static lookup when ordering is unnecessary, accepting their different memory, precision, or worst-case trade-offs. section 6.1.1
- Use randomized treaps when average-case guarantees are acceptable; small trees can still become skewed, although the practical performance gap is smaller. section 3.4.3
Operational uses
Sorted dynamic sets can keep stream data ordered, count elements smaller or larger than a given value, manage virtual memory areas in operating-system kernels, or track packet IP verification IDs. A hash table may be faster for the last case but can degrade under collision-heavy attacks. section 3.4.3
Figure 6.1 A BST storing (part of) a dictionary, and the steps to search the word “antic”. In this example, it’s a miss because the word was not stored in the tree shown.
Trace a binary-search-tree lookup through its nodes to see how ordered search proceeds and how a miss is identified. section 6.1.1
