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