[Java] TreeMap successor method and entrySet complexity

Succcessor Method

As we know TreeMap is implemented by Binary Search Tree. So I am very curious about the entrySet or subMap method implementation and complexity.

It turns out java do it very straight forward. For entrySet, it start from the first node and by finding successor to move to next node.

It has a successor method to find next node by the following steps.

/**
 * Returns the successor of the specified Entry, or null if no such.
 */
static <K,V> TreeMap.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;
    }
}

Complexity About the complexity, here has a good explain. Assume we go through a balanced BST. We can separate it as two parts.

The average steps is 2 according to the explain here.sotheaveragecomplexityofsuccessorisO(1)andthecomplexityofgoingthroughallelementswithentrySetisO(n).

Recommended Posts

[Java] TreeMap successor method and entrySet complexity
Java methods and method overloads
[Java beginner] == operator and equals method
java (method)
Java method
[Java] method
[Java] method
Java Silver exam procedure and learning method
[Java] Collection and StringBuilder operation method comparison
Java8 method reference
[Java] forEach method
variable and method
XXE and Java
java8 method reference
[Java] Random method
[Java] split method
JAVA DB connection method
Getters and setters (Java)
[Java] Thread and Runnable
Java learning 2 (learning calculation method)
Java true and false
Java learning memo (method)
[Java] String comparison and && and ||
About Java method binding
[Java ~ Method ~] Study memo (5)
Studying Java 8 (see method)
Java programming (class method)
Java --Serialization and Deserialization
[Java] Arguments and parameters
timedatectl and Java TimeZone
[Java] Branch and repeat
[Java] Variables and types
[Java] Basic method notes
java (classes and instances)
[Java] Overload and override
[Java] Comparison method of character strings and comparison method using regular expressions