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
$\Theta (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