Java TreeSet 中的给定元素位于第几层？
有谁知道一种快速方法来检测给定元素在 TreeSet？所谓级别，是指该元素在树中的深度，即其祖先的数量。
背景。 我使用 Java 的 TreeSet 类来存储我的元素。 为了比较两个元素，我需要计算一些关于它们的辅助信息。我无法存储每个元素的辅助信息，因为它会占用太多内存。 另一方面，如果我为每次比较重新生成辅助信息，我的程序就太慢了。 当将元素插入到 TreeSet 中时，我当前的实现会计算它插入的元素的辅助信息，并且直到该元素在 TreeSet 中找到其位置时才重新计算它。之后，辅助信息被丢弃。 为了加速我的程序，我想也存储 TreeSet 顶层的辅助信息，因为它们涉及许多比较。因此，在比较两个节点之后，我想根据它们在 TreeSet 中的深度来决定是否保留或丢弃它们的辅助信息。
更新。 如果有人可以建议一个替代类实现某种平衡树（AVL树，红/黑树，Splay树，...），并且可以访问高度，我也将不胜感激一个元素的。
Does anybody know a fast way to detect at what level a given element is in a TreeSet? By level, I mean the depth of this element in the tree, i.e. the number of its ancestors.
Background.
I use Java's TreeSet class to store my elements.
To compare two elements I need to compute some auxiliary information about them. I cannot store this auxiliary information for each element as it would take too much memory.
On the other hand, if I regenerate the auxiliary information for each comparison, my program is too slow.
When an element is inserted in the TreeSet, my current implementation computes the auxiliary information for the element it inserts and does not recompute it until the element has found its place in the TreeSet. Afterwards, the auxiliary information is discarded.
To speed up my program, I would like to store the auxiliary information also for the top levels of the TreeSet, as they are involved in many comparisons. So, after comparing two nodes, I would like to decide whether to keep or discard their auxiliary information based on their depth in the TreeSet.
Update.
I would also be grateful if somebody could suggest an alternate class implementing some kind of balanced trees (AVL trees, red/black trees, Splay trees, ...), and where one has access to the height of an element.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
TreeSet根本不公开每个节点的确切深度。如果您想这样做，则必须自己编写。您也许可以执行诸如让集合中的每个键引用管理辅助信息的共享对象之类的操作。每次在某个键上调用
compareTo()时，它都会通知管理器更新该键的计数器。经理将使用这些统计数据来决定哪些人应该维护其辅助信息。The exact depth of each node is simply not exposed by a
TreeSet. You'd have to write your own if this is how you want to do it.You might be able to do something like have each key in the set refer to a shared object that manages the auxiliary information. Each time
compareTo()is invoked on a key, it would notify the manager to update its counter for that key. The manager would use these stats to decide which should maintain their auxiliary information.