• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Tim Cooke
  • Ron McLeod
  • Jeanne Boyarsky
  • Paul Clapham
Sheriffs:
  • Liutauras Vilda
  • Henry Wong
  • Devaka Cooray
Saloon Keepers:
  • Tim Moores
  • Stephan van Hulst
  • Tim Holloway
  • Al Hobbs
  • Carey Brown
Bartenders:
  • Piet Souris
  • Mikalai Zaikin
  • Himai Minh

java's TreeMap implementation - Algorithm ?

 
Ranch Hand
Posts: 1491
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Whether java's TreeMap implementation is Binary Search Tree Algorithm ?
 
author
Posts: 23926
142
jQuery Eclipse IDE Firefox Browser VI Editor C++ Chrome Java Linux Windows
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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

Henry
 
kri shan
Ranch Hand
Posts: 1491
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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.
 
Java Cowboy
Posts: 16084
88
Android Scala IntelliJ IDE Spring Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
author
Posts: 23926
142
jQuery Eclipse IDE Firefox Browser VI Editor C++ Chrome Java Linux Windows
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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
 
Consider Paul's rocket mass heater.
reply
    Bookmark Topic Watch Topic
  • New Topic