File APIs for Java Developers
Manipulate DOC, XLS, PPT, PDF and many others from your application.
http://aspose.com/file-tools
The moose likes Beginning Java and the fly likes java's TreeMap implementation - Algorithm ? Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of Head First Android this week in the Android forum!
JavaRanch » Java Forums » Java » Beginning Java
Bookmark "java Watch "java New topic
Author

java's TreeMap implementation - Algorithm ?

kri shan
Ranch Hand

Joined: Apr 08, 2004
Posts: 1396
Whether java's TreeMap implementation is Binary Search Tree Algorithm ?
Henry Wong
author
Sheriff

Joined: Sep 28, 2004
Posts: 19929
    
  43


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

Henry


Books: Java Threads, 3rd Edition, Jini in a Nutshell, and Java Gems (contributor)
kri shan
Ranch Hand

Joined: Apr 08, 2004
Posts: 1396
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
Java Cowboy
Saloon Keeper

Joined: Aug 16, 2005
Posts: 14917
    
  26

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


Java Beginners FAQ - JavaRanch SCJP FAQ - The Java Tutorial - Java SE 8 API documentation
Henry Wong
author
Sheriff

Joined: Sep 28, 2004
Posts: 19929
    
  43

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
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: java's TreeMap implementation - Algorithm ?
 
It's not a secret anymore!