如何查找 TreeSet 中元素的排名
我知道你可以找到树集中的第一个和最后一个元素。如果我想知道第二个或第三个元素是什么而不进行迭代怎么办？或者，更可取的是，给定一个元素，找出它在树集中的排名。
谢谢
编辑：我认为你可以使用 tailset 来做到这一点，即。将原始组的大小与尾组的大小进行比较。 tailset 的效率如何？
I know you can find the first and last elements in a treeset. What if I wanted to know what the second or third element was without iterating? Or, more preferable, given an element, figure out it's rank in the treeset.
Thanks
EDIT: I think you can do it using tailset, ie. compare the size of the original set with the size of the tailset. How efficient is tailset?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
TreeSet没有提供有效的排序方法。我怀疑（您可以通过查看其源代码来确认）TreeSet 甚至不维护任何额外的信息位（即每个节点的左子树和右子树上的元素计数），而这些信息是人们需要的在 O(log(n)) 时间内执行此类查询。因此，似乎没有任何快速方法可以查找TreeSet元素的排名。如果您确实需要它，您可以使用允许此类查询的平衡二叉搜索树实现自己的
SortedSet，或者修改TreeSet实现以创建一个新的实现，该实现是增强以允许此类查询。有关如何实际完成此操作的更多详细信息，请参阅有关 CLRS 中的数据结构增强的章节。TreeSetdoes not provide an efficient rank method. I suspect (you can confirm by looking at its source) thatTreeSetdoes not even maintain any extra bits of information (i.e. counts of elements on the left and right subtrees of each node) that one would need to perform such queries in O(log(n)) time. So there does not appear to be any fast method of finding the rank of an element ofTreeSet.If you really really need it, you can either implement your own
SortedSetwith a balanced binary search tree which allows such queries or modify theTreeSetimplementation to create a new implementation which is augmented to allow such queries. Refer to the chapter on augmenting data structures in CLRS for more details about how this can actually be done.根据Sun JDK6实现的源码，
tailSet(E).size()会迭代tail set并计算元素数量，因此这个调用的时间复杂度为O(tail set size)。According to the source of the Sun JDK6 implementation,
tailSet(E).size()iterates over the tail set and counts the elements, so this call is O(tail set size).除了迭代器之外没有其他方法。
编辑：
试试这个：
这应该给出 TreeSet 上的第二个元素。我不确定这是否比使用迭代器更优化。
There is no other way than Iterator.
Edited:
Try this:
This should give second element on TreeSet. I'm not sure if this is more optimized then just using Iterator.