在我的代码中,JavaTreeSet迭代是主要的时间因素。在观察这个系统时,我相信它的复杂度是 O(n) 。任何人都可以验证这一点吗?
我认为通过提供从子节点到父节点的向后链接我可以提高性能。
TreeSet
迭代当然是 O(n),正如任何合理的树遍历算法所期望的那样。
我想通过提供链接
从子节点向后到父节点
节点我可以提高性能。
TreeMap
(which 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;
}
}
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)