bombax bombax - 6 months ago 35
Java Question

Data structure with logarithmic insert/delete and "no-greater-than"

I'm solving a coding challenge right now, and I have a solution, but for it to work, I need a data structure which supports four operations:

  • Insertion in O(log(N))

  • Deletion in O(log(N))

  • Checking how many elements are greater than a specified element in O(log(N))

  • Checking how many elements are less than a specified element in O(log(N))

I tried solving it using Java's
which can support these operations by
(and checking the size of the two last ones). But this solution is too slow. I haven't checked the time complexities but I have a feeling that
do not run in logarithmic time (or run inefficiently).

Does anyone know of a data structure I can implement to support these operations? Is it even possible? And, if it is in some tree shape, preferably self-balancing?


As mentioned in the comments above, "Order statistic trees" solved the problem I asked for elegantly, and in addition, were relatively easy to implement, and ultimately gave me an accepted submission for the challenge. Thanks!