Java中的TreeSet的lower()/更高()的时间复杂度是多少？

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了Java中的TreeSet的lower()/更高()的时间复杂度是多少？，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含951字，纯文字阅读大概需要2分钟。

内容图文

我知道add,get等基本操作的时间复杂度是O(logn).但我没有找到lower()和更高()的细节.那么,Java中的TreeSet的lower()和更高()的时间复杂度是多少？

解决方法:

TreeSet由名为TreeMap的NavigableMap实现支持.在TreeSet上计算lower()时最终调用的代码是TreeMap上的lowerEntry().

/**
 * Returns the entry for the greatest key less than the specified key; if
 * no such entry exists (i.e., the least key in the Tree is greater than
 * the specified key), returns {@code null}.
 */
final Entry<K,V> getLowerEntry(K key) {
    Entry<K,V> p = root;
    while (p != null) {
        int cmp = compare(key, p.key);
        if (cmp > 0) {
            if (p.right != null)
                p = p.right;
            else
                return p;
        } else {
            if (p.left != null) {
                p = p.left;
            } else {
                Entry<K,V> parent = p.parent;
                Entry<K,V> ch = p;
                while (parent != null && ch == parent.left) {
                    ch = parent;
                    parent = parent.parent;
                }
                return parent;
            }
        }
    }
    return null;
}

查看此代码,看起来与while循环的每次迭代一样,每个分支返回或遍历树的一个级别.由于树映射应具有log(n)级别,因此整个方法具有O(log(n))复杂度.

内容总结

以上是互联网集市为您收集整理的Java中的TreeSet的lower()/更高()的时间复杂度是多少？全部内容，希望文章能够帮你解决Java中的TreeSet的lower()/更高()的时间复杂度是多少？所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端