bombax - 7 months ago 38

Java Question

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`

`add`

`remove`

`headSet`

`tailSet`

`...set`

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!

Source (Stackoverflow)