什么是TreeSet中迭代的时间复杂？ [英] What is the time complexity of TreeSet iteration?

问题描述

在我的code，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屋！