I need a data structure that that stores a subset—call it S—of {1, . . . , n} (n given initially) and supports just these operations:
• Initially: n is given, S = {1, . . . , n} at the beginning.
• delete(i): Delete i from S. If i isn't in S already, no effect.
• pred(i): Return the predecessor in S of i. This means max{j ∈ S | j < i}, the greatest element in S that is strictly less than i. If there is none, return 0. The parameter i is guaranteed to be in {1, . . . , n}, but may or may not be in S.
For example, if n = 7 and S = {1, 3, 6, 7}, then pred(1) returns 0, pred(2) and pred(3) return 1.
I need to figure out:
- a data structure that represents S
- an algorithm for initialization (O(n) time)
- an algorithm for delete (O(α(n)) amortized time)
- an algorithm for pred (O(α(n)) amortized time)
Would appreciate any help (I don't need code - just the algorithms).