Preliminary Approaches
Summarized notes on Introduction to Algorithms, Chapter 20
General Notes
- \(u\) - universe size;
- \({0,1,2,... u-1}\) values can be stored in this universe
- \(n\) - number of elements currently in the set
Direct addressing
- use array of \(u\) bits to store values
- 1 means value is in set, 0 means it is not
- issue: long scans through elements
| time | |
|---|---|
| \(O(1)\) | insert, delete, member |
| \(Θ(u)\) | min, max, successor, predecessor |
Superimposed binary tree
- Pair array with binary tree where array as the leaf nodes
- Each tree node summarizes its children
- Internal node will have 1 if its subtree contains 1 (logical-or)
- Update relevant binary tree nodes on insert/delete
- pro: avoid long array searches (but still not good enough)
| time | |
|---|---|
| \(O(1)\) | member |
| \(O(\log u)\) | insert, delete, min, max, successor, predecessor |
Superimposing tree of constant height
- impose tree of degree \(\sqrt u\) → tree height is always 2
- each internal node still stores summary bit for its respective cluster
- issue: asymptotic time increases
| time | |
|---|---|
| \(O(1)\) | insert, member |
| \(O(\sqrt u)\) | delete, min, max, successor, predecessor |