Высота TreeSet в Java? - PullRequest
Новая
       33

Высота TreeSet в Java?

0 голосов
/ 07 июня 2018

Можно ли рассчитать точную высоту красно-черного дерева, используемого в классе TreeSet в Java?Меня не волнует сложность времени.

Более того, возможно ли узнать, сколько дочерних элементов (0 или 2) имеет узел в объекте TreeSet.

Обратите внимание, что мы нене имеет доступа ни к чему, кроме ссылки на объект TreeSet.

1 Ответ

0 голосов
/ 07 июня 2018

Учитывая только ссылку, вы ничего не можете сделать без отражения.С отражением в TreeSet экземпляре T вы захотите:

  1. получить доступ к его поддержке NavigableMap, которая по умолчанию будет TreeMap.Давайте назовем его M.
  2. доступ к корню M типа TreeMap.Entry
  3. , использующий простой рекурсивный алгоритм для получения глубины (максимальная глубина = высота) и любой другой информации об узлах.

Это может показаться пугающим, но на самом деле все гораздо проще, чем кажется: 

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);
    }
}

Обратите внимание, что мы не можем явно указать тип узлов, поскольку класс 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
...