bombax bombax - 1 month ago 6
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
TreeSet
which can support these operations by
add
,
remove
,
headSet
and
tailSet
(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
...set
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?

Answer

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!