Java 中 TreeSet 的高度？

Question

是否可以计算 Java 中 TreeSet class 中使用的红黑树的确切高度？我根本不关心时间复杂度。

此外，是否可以知道一个节点在TreeSet对象中有多少个子节点（0个或2个）。

请注意，除了对 TreeSet 对象的引用之外，我们无权访问任何内容。

Answer 1

仅供参考，不思则行。通过对 TreeSet 实例 T 的反思，您将需要：

访问其支持 NavigableMap，默认情况下将是 TreeMap。暂且称它为M.
访问 M 的根，类型为 TreeMap.Entry
使用简单的递归算法获取深度（最大深度 = 高度）和节点上的任何其他信息。

这可能看起来令人生畏，但实际上比看起来容易得多：

public class TreeSpy {

    private static Object get(Object o, String fieldName) {
        try {
            Field declaredField = o.getClass().getDeclaredField(fieldName);
            declaredField.setAccessible(true);
            return declaredField.get(o);
        } catch (Exception e) {
            System.err.println("Could not gain access to field "
                    + fieldName + " of " + o.getClass());
            e.printStackTrace();
            return null;
        }
    }

    private static int diveInto(Object n, int depth, String indent) {
        if (n == null) return depth-1; // we are empty, and should not be counted
        Object left = get(n, "left");
        Object right = get(n, "right");
        String key = (String)get(n, "key");

        int childrenCount = 0 + (left!=null?1:0) + (right!=null?1:0);
        System.out.println(indent + key +
                ": depth=" + depth + ", chidren=" + childrenCount);
        return Math.max(
                diveInto(left,  depth+1, indent+"  "),
                diveInto(right, depth+1, indent+"  "));
    }

    public static void showDepthAndChildren(TreeSet<String> set) {
        TreeMap<String, Object> m = (TreeMap<String, Object>)get(set, "m");
        Object root = get(m, "root");
        int maxDepth = diveInto(root, 1, "");
        System.out.println("Height = Max Depth = " + maxDepth);
    }

    public static void main(String ... args) {
        TreeSet<String> test = new TreeSet<>();
        for (String s : "once upon a time in a galaxy far far away".split(" ")) {
            test.add(s);
        }
        showDepthAndChildren(test);
    }
}

请注意，我们不能明确提及节点类型，因为 class TreeMap.Entry 具有私有访问权限。但是，我们仍然可以使用该类型的对象来检查属性。

我的机器（JDK8）上的输出是：

once: depth=1, chidren=2
  galaxy: depth=2, chidren=2
    away: depth=3, chidren=2
      a: depth=4, chidren=0
      far: depth=4, chidren=0
    in: depth=3, chidren=0
  upon: depth=2, chidren=1
    time: depth=3, chidren=0
Height = Max Depth = 5

Java 中 TreeSet 的高度？

Height of a TreeSet in Java?

java

algorithm

data-structures

red-black-tree