We want to store a set S of distinct positive integers and support the following operations on S:
Insert(a): insert integer a !∈ S into S.
Delete(a): delete integer a ∈ S from S.
FindNext(a, k), where a ∈ S and k is an integer: if S consists of some elements a1 < a2 < · · · < an, and a = ai (for some i, 1 ≤ i ≤ n), then return ai+k (for simplicity, assume that i + k ≤ n).
The worst-case time complexity of each operation should be O(log n) where n is the size of S. An augmented data structure can be used (without any modification) “as a black box” to achieve the above goal: using the operations that this data structure provides, the algorithms for performing the above three operations are quite simple. Give an algorithm for the FindNext(a, k) operation that uses only the operations of this data structure and consists of at most 5 lines of pseudo-code.
You are allowed to make use of other operations available with this data structure, i.e. everything you can make run in the specified time.