-4

i am good with the implementation part, i just want to know how the values will be inserted in tree map based on the Comparator or comparable. please don't just give the implementation of comparable and Comparator.

Basically i want to know how different Comparable and Comparator are when it comes to insertion of values in Red Black Tree(underlying data structure of TreeMap). how the insertion will be done.? if it is comparable, with which object inserted object will be compared? if it is Comparator, which two objects would be compared to get the appropriate position in tree. it would be great if there is an example

Narahari Babu Kannemadugu
  • 31
  • 5

1 Answers1

1

TreeMap and TreeSet are basically binary trees. Due to this the position where a node can be found/will be insert can be found easily using binary search:

//just a stub of how the search for a specific node might work (this is not the real implementation
Node currentNode = ...
if(comparator.compare(currentNode.content , toSearch) < 0)
    currentNode = currentNode.leftNode();
else
    ...
  • Thanks for the answer paul. even i am aware of that internal data structure for TreeMap is Red Black Tree.i wanted to know how differently these two works when we actually insert values. let's say comparable compares object with itself and comparator compares objects of two same types. when it comes to the insertion part in the Red Black Tree how both will work?? it would be great if you can explain with any example. – Narahari Babu Kannemadugu Oct 05 '15 at 12:54
  • @NarahariBabuKannemadugu ah, ok, i've misunderstood the question. that's pretty simple: `a.compareTo(b)` should always produce the same output as `someComparator.compare(a , b)`. Thus we can simply switch any of these two lines with the other, to compare values. The rest is just matching signatures for the methods for insertion/removal. –  Oct 05 '15 at 12:59
  • @NarahariBabuKannemadugu you should probably change the question to something more matching, like "how are Comparator and Comparable interchangeable"? Just something that matches the question more accurately –  Oct 05 '15 at 13:03
  • ohh.. thank you Paul. so, it basically comparison starts from the root node of the tree i.e a in our case and b is our inserted object and based on Red Black tree principle object will be placed in the appropriate node. am i right?? – Narahari Babu Kannemadugu Oct 05 '15 at 13:08
  • @NarahariBabuKannemadugu exactly –  Oct 05 '15 at 14:41