?
Solved

JAVA: RB Tree Map

Posted on 2011-10-27
6
Medium Priority
?
292 Views
Last Modified: 2012-05-12
I need to build my own Red Black tree class in Java. All the algorithms including get, put, remove, etc need to be based on 2-3-4 trees, but the overall structure has to look like a Red Black tree.

I'm not even sure where to begin. See what's needed below.

class RBTreeMap
{
public RBTreeMap();
public void clear();
public boolean containsKey(Object key);
public boolean containsValue(Object value);
public V get(Object key);
public V put(K key, V value);
public V remove(Object key);
public int size();
public ArrayList display();
};

All of these functions must function as EXACT identical copies of those found in java.util.TreeMap. Your RBTreeMap must behave in exactly the same way, in all respects, that java.util.TreeMap would behave if substituted.
0
Comment
Question by:InfoTechEE
  • 4
  • 2
6 Comments
 
LVL 28

Expert Comment

by:dpearson
ID: 37051050
If this is a homework project I think you should read up on how Red Black trees work.  Probably best to start by just implementing a simple tree map yourself, where new items are inserted into a tree.  Once you have that working you can then try to work on the auto balancing part.

These will help explain the algorithm:
http://eternallyconfuzzled.com/tuts/datastructures/jsw_tut_rbtree.aspx
http://en.wikipedia.org/wiki/Red%E2%80%93black_tree

If this is not a homework problem you could look at this implementation:
http://www.java-tips.org/java-se-tips/java.lang/red-black-tree-implementation-in-java.html

However, if this is homework I'd stay away from that link.  It'll be very obvious to your teacher if you just pull this code over rather than figuring it out yourself and really understanding how to build a red black tree.  And of course the whole point of a project like this is to gain that understanding, not just have a piece of working code.

Good luck!

Doug
0
 

Author Comment

by:InfoTechEE
ID: 37051649
This is a homework assignment, and I am trying to figure this out on my own. I am pretty familiar with RB trees and 2-3-4 trees and on paper can do all sorts of things, however, programming it has proven very difficult.

Right now, I'm stuck on containsValue. How do you search a red black tree by value. containsKey was easy because Keys are stored in a comparable order. Values on the other hand can be sorted in any way, so when you are at the root node looking for a value, how do you make the decision whether to look left or to look right?
0
 
LVL 28

Expert Comment

by:dpearson
ID: 37051814
For containsValue() you're right that there's no way to do an efficient search.  The best you can do is scan every element in the tree checking each in turn.

That's ok.  TreeMap's containsValue() is also O(n) where n is the elements in the map.

Doug

0
What does it mean to be "Always On"?

Is your cloud always on? With an Always On cloud you won't have to worry about downtime for maintenance or software application code updates, ensuring that your bottom line isn't affected.

 
LVL 28

Accepted Solution

by:
dpearson earned 2000 total points
ID: 37051820
BTW if you're not sure how to walk the entire tree - the simplest is a recursive algorithm, something like:

public boolean visitNode(Node n, Object value) {
    if (n.value.equals(value))
       return true ;
    if (n.left == null && n.right == null)
       return false ;
    boolean found = n.left != null ? visitNode(n.left) : false ;
    found = found || (n.right != null ? visitNode(n.right) : false) ;
    return found ;
}
0
 

Author Comment

by:InfoTechEE
ID: 37054239
So I didn't want to copy the code you gave, and wanted to come up with something on my own. I briefly looked at your code, and simply took one thing away -- "Recursion". I closed the webpage, and built my own version without further glansing at your code. My version came out a lot more complex, but at least it's my own work. :)

Can you please glance over it and tell me if it makes sense or if I have errors anywhere. Thanks.

public boolean containsValue(Object value)
{
   Node<K,V> n = root;
   if(n==null)
      return false;
   else return containsValueHelper(n,value);
}
      
public boolean containsValueHelper(Node<K,V> x, Object value)
{
   boolean containsVal = false;
   if(x.value == value)
      return true;
   if(x.left != null)
      containsVal = containsValueHelper(x.left,value);
   if((x.right != null)&&(containsVal==false))
         containsVal = containsValueHelper(x.right,value);
   return containsVal;
}
0
 
LVL 28

Expert Comment

by:dpearson
ID: 37054748
Yes that looks basically correct to me and good for you for writing it yourself.  And your version is actually very close to mine.

The only error I can see is that this line:

if(x.value == value)
      return true;

should really be:

if (x.value.equals(value))
   return true ;

A == B is only true if they're the exact same object.

E.g.
Integer A = new Integer(10);
Integer B = new Integer(10) ;
(A == B) will be false but (A.equals(B)) will be true.

Doug
0

Featured Post

Technology Partners: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

This was posted to the Netbeans forum a Feb, 2010 and I also sent it to Verisign. Who didn't help much in my struggles to get my application signed. ------------------------- Start The idea here is to target your cell phones with the correct…
Go is an acronym of golang, is a programming language developed Google in 2007. Go is a new language that is mostly in the C family, with significant input from Pascal/Modula/Oberon family. Hence Go arisen as low-level language with fast compilation…
Video by: Michael
Viewers learn about how to reduce the potential repetitiveness of coding in main by developing methods to perform specific tasks for their program. Additionally, objects are introduced for the purpose of learning how to call methods in Java. Define …
Viewers learn about the scanner class in this video and are introduced to receiving user input for their programs. Additionally, objects, conditional statements, and loops are used to help reinforce the concepts. Introduce Scanner class: Importing…
Suggested Courses
Course of the Month17 days, 6 hours left to enroll

864 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question