Design a data structure for holding numbers in two sets:
Init - initiate the DS with two empty sets.
Insert(a,S) - insert number
a to set
S could be
O(log(n)). (n is the total number of numbers in the DS)
Find - find a number
a in the DS such that the number of numbers in
X that are smaller than
a equals the number of numbers in
Y that are bigger than
a, if exists such number.
My attempt is using 2 augmented balanced binary search trees, each one presents set
Y, insert into it the new number and saving in each node information for finding what is the number of numbers in
X that are smaller than this node and the number of numbers on
Y that are bigger than that node.
But given that information how could I implement the
Find procedure in
O(1)? Or maybe someone have better design (preferably using augmented BST)?