What is the time complexity of the lower () / higher () TreeSet method in Java?

Question

I know the time complexity of basic operations like add, get is O (logn). But I did not find the details of lower () and higher (). So what is the time complexity of the lower () and higher () TreeSet method in Java?

Answer 1

TreeSet is supported by a NavigableMap implementation called TreeMap. The code that is ultimately called when lower () is calculated in the TreeSet is lowerEntry () on the TreeMap.

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

Looking at this code, it looks like with each iteration of the while loop, each branch returns or traverses one level of the tree. Since the tree map must have levels log(n), the whole method has complexity O(log(n)).

Answer 2

, get(), O (log n).

lower() higher() a get(); get(), ( ) node. , 2, , O (log n) .

Answer 3

, - OpenJDK 8 - O (log n).

TreeSet TreeMap ( , ), lower() TreeMap:: lowerKey ( m NavigableMap, , , TreeMap).

TreeMap:: lowerKey, , getLowerEntry, , ; O (log n) (, - , TreeMap).

TreeSet:: higher() .

Answer 4

Java TreeSet TreeMap - () (BST). (: lower() higher() ) - BST, 2 log N.

, O (log N).