java's TreeMap implementation - Algorithm ?

[kri shan]

Whether java's TreeMap implementation is Binary Search Tree Algorithm ?

[Henry Wong]

The javadoc (actually reachable from your post) actually talks about the implementation. In fact, it is mentioned right in the beginning.

Henry

[kri shan]

As per the java doc

Algorithms are adaptations of those in Cormen, Leiserson, and Rivest's Introduction to Algorithms.

. I do not see binary search algorithm.

[Jesper de Jong]

If you want to know all the details, then you can lookup the source code for class TreeMap. In your JDK installation directory, there is a file named src.zip. In there you will find the source code for all the standard Java API classes, including the source code for java.util.TreeMap.

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: ...

[Henry Wong]

kri shan wrote:As per the java doc

Algorithms are adaptations of those in Cormen, Leiserson, and Rivest's Introduction to Algorithms.

. I do not see binary search algorithm.

As already mentioned by Jesper; it is mentioned in the JavaDoc in the very first sentence,

A Red-Black tree based NavigableMap implementation.

Henry