TreeSet迭代的时间复杂度是多少？ [英] What is the time complexity of TreeSet iteration?

问题描述

在我的代码中，Java TreeSet 迭代是主要的时间因素。在看系统的时候，我认为这是O（n）的复杂性。任何人都可以验证这个？

In my code, Java TreeSet iteration is the dominant time factor. In looking at the system I believe that it is O(n) complexity. Can anyone verify this?

我认为通过从子节点向父节点提供链接，我可以提高性能。

I am thinking that by providing links backward from child node to parent node I could improve the performance.

推荐答案

TreeSet 迭代当然是O（n），可以期望从任何明智的树行走算法。

TreeSet iteration is of course O(n), as can be expect from any sensible tree-walking algorithm.

我想通过从子节点向父
返回提供链接
可以提高性能。

I am thinking that by providing links backward from child node to parent node I could improve the performance.

TreeMap （其中 TreeSet 基于）已经有这样的父引用。这是所有归结的方法：

TreeMap (which TreeSet is based on) already has such parent references. This is the method it all boils down to:

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

这篇关于TreeSet迭代的时间复杂度是多少？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！