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.
- if current node is null, then no next, return null
- if current node has right child
- find the most left one of right child as next node
- if current node does not have right child, check current node is left or right child
- if it is left child, the parent is next code
- if it is right child, then go back to parent
/**
* 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 leaf nodes
- All other nodes
The average steps is 2 according to the explain here. so the average complexity of successor is O(1) and the complexity of going through all elements with entrySet is O(n).