java - 如何在 TreeSet 中查找元素的排名

Question

我知道您可以在树集中找到第一个和最后一个元素。如果我想知道第二个或第三个元素是什么而不进行迭代怎么办？或者，更可取的是，给定一个元素，找出它在树集中的排名。

谢谢

编辑：我认为你可以使用 tailset 来做到这一点，即。将原始集的大小与尾集的大小进行比较。tailset 的效率如何？

Answer 1

TreeSet没有提供有效的排名方法。我怀疑（你可以通过查看它的来源来确认）它TreeSet甚至没有维护任何额外的信息位（即每个节点的左右子树上的元素计数）需要在 O(log( n)) 时间。所以似乎没有任何快速的方法来找到 的元素的等级TreeSet。

如果您真的需要它，您可以使用SortedSet允许此类查询的平衡二叉搜索树来实现您自己的，或者修改TreeSet实现以创建一个新的实现，该实现被增强以允许此类查询。有关如何实际完成此操作的更多详细信息，请参阅关于在 CLRS 中扩充数据结构的章节。

Answer 2

除了迭代器，别无他法。

编辑：

试试这个：

treeSet.higher(treeSet.first());

这应该在 TreeSet 上给出第二个元素。我不确定这是否比仅使用迭代器更优化。

Answer 3

根据 Sun JDK6 实现的源码，tailSet(E).size()迭代尾集并计算元素，所以这个调用是 O(tail set size)。