As the documentation says, it is implemented with a red-black tree. And Wikipedia says:
A red-black tree is a binary search tree where each node has a color attribute, the value of which is either red or black. In addition to the ordinary requirements imposed on binary search trees, the following additional requirements apply to red-black trees: ...
kri shan wrote:As per the java doc
. I do not see binary search algorithm.
Algorithms are adaptations of those in Cormen, Leiserson, and Rivest's Introduction to Algorithms.
As already mentioned by Jesper; it is mentioned in the JavaDoc in the very first sentence,
A Red-Black tree based NavigableMap implementation.