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

Question

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

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

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

7

java algorithm data-structures treeset

задан John Smith 3 May 2010 в 21:58

2 ответа

Другие вопросы по тегам:

java algorithm data-structures treeset

Похожие вопросы:

score 4 · 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;
    }
}

score 1 · Answer 2

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