java - Java TreeSet 中的给定元素处于什么级别？

Question

有没有人知道一种快速检测给定元素在 TreeSet 中的级别的方法？ ？层级是指该元素在树中的深度，即其祖先的数量。

背景。我使用 Java 的 TreeSet 类来存储我的元素。为了比较两个元素，我需要计算关于它们的一些辅助信息。我无法为每个元素存储这些辅助信息，因为它会占用太多内存。另一方面，如果我为每次比较重新生成辅助信息，我的程序就太慢了。当一个元素被插入到 TreeSet 中时，我当前的实现计算它插入的元素的辅助信息，并且直到该元素在 TreeSet 中找到它的位置时才重新计算它。之后，辅助信息被丢弃。为了加快我的程序，我还想为 TreeSet 的顶层存储辅助信息，因为它们涉及许多比较。因此，在比较两个节点之后，我想根据它们在 TreeSet 中的深度来决定是保留还是丢弃它们的辅助信息。

更新。如果有人可以建议替代类实现某种平衡树(AVL 树、红/黑树、Splay 树...)，并且可以访问高度，我也将不胜感激一个元素。

Answer 1

TreeSet 根本不会公开每个节点的确切深度。如果您希望这样做，则必须自己编写。

您可以做一些事情，比如让集合中的每个键都引用一个管理辅助信息的共享对象。每次在键上调用 compareTo() 时，它都会通知管理器更新该键的计数器。经理将使用这些统计信息来决定哪些应该维护他们的辅助信息。