[An order statistic tree to JDK?]

[-]

The order statistic for a tree map/set appears easily supported with
an additional size field for each tree node. Don't think we need a new
AVL tree implementation if we desire that functionality. However,
before all, do we really need this functionality of accessing an
object by index? We need a few use cases for this functionality, and
see if this is the best way to cover those cases.

Note: You can already get the index of an input object, in O(log n)
with headMap/headSet. So I only consider the question of accessing an
object by rank/index.

On Tue, Jun 14, 2022 at 10:46 PM Rodion Efremov <coderodd3 at gmail.com> wrote:
>
> Hello community,
>
> I have implemented an order statistic tree using the ALV algorithm and, thus, running all single element methods in worst case logarithmic time [1]. Basically, it’s a sorted list that allows:
> (1) accessing the ith element in O(log n),
> (2) getting the index of an input object, runs also in O(log n).
>
> What do you think? Does it have a chance of ending up in JDK?
>
> Best regards,
> rodde
>
> [1]
> https://github.com/coderodde/OrderStatisticTree/blob/master/src/main/java/net/coderodde/util/OrderStatisticsTree.java
>