Какова временная сложность итерации TreeSet?

Question

В моем коде Java TreeSet итерация является доминирующим фактором времени. Глядя на систему, я считаю, что это сложность O (n). Кто-нибудь может это проверить?

Я думаю, что, предоставляя ссылки назад от дочернего узла к родительскому узлу, я мог бы улучшить производительность.

Answer 1

TreeSet итерация - это, конечно, O (n), что можно ожидать от любого разумного алгоритма обхода дерева.

Я думаю, что, предоставляя ссылки назад от дочернего узла к родительскому узел я мог бы улучшить производительность.

TreeMap (на котором основан TreeSet) уже имеет такие родительские ссылки. Это метод, который сводится к следующему:

private Entry<K,V> successor(Entry<K,V> t) {
    if (t == null)
        return null;
    else if (t.right != null) {
        Entry<K,V> p = t.right;
        while (p.left != null)
            p = p.left;
        return p;
    } else {
        Entry<K,V> p = t.parent;
        Entry<K,V> ch = t;
        while (p != null && ch == p.right) {
            ch = p;
            p = p.parent;
        }
        return p;
    }
}

Answer 2

Рассматривали ли вы возможность использования копии TreeSet при ее изменении? Если доминирующее время тратится на итерацию TreeSet (а не на ее изменение), то копирование TreeSet в массив или ArrayList (только при изменении) и только итерации по этому массиву / ArrayList могут практически исключить стоимость итерации TreeSet.