java - 使用子树大小扩展 Java TreeSet

Question

我想将 Java TreeSet 扩展到 Order-Statistics 树。因此，我的想法是我将子树大小存储在每个节点中，并操作add()和remove()方法 st 子树大小也将被更新。

我知道有一些数据结构（也在 Java 中）已经实现了这一点，但我的问题是是否有可能以某种方式扩展 TreeSet 类，每当我修改数据结构时，这个属性就会被存储和更新。

Answer 1

如果您查看源代码，aTreeSet有一个

private transient NavigableMap<E,Object> m;

您当然可以实现add,addAll等remove，但TreeSet大多数方法只是调用底层 Map，即private，因此您的实现无法访问。似乎Order-Statistic-Tree 可以具有与普通 TreeMap 不同的顺序，这似乎无法通过扩展 TreeSet 来实现。

使用另一种数据结构

您应该能够将数据结构基于TreeMap，据称 TreeSet 就是基于该结构。它

为 containsKey、get、put 和 remove 操作提供有保证的 log(n) 时间成本。