?
Solved

Splay Tree insert() issue PART 2

Posted on 2004-11-11
18
Medium Priority
?
258 Views
Last Modified: 2008-01-09
So now my grabnode() is having trouble handling the case where the node that is trying to get inserted already exists (in this case, i want to return that nodes key value when it is found in the tree, so i may change its item value in the insert method) instead I get a java.lang.classCastException when a duplicate arises.
      public void insert(Object key, Object item){
            TreeNode parentNode, n, newNode;
            Object nObj;
            parentNode = null;
            if (isEmpty()) {
                _root = new TreeNode(key, item);
            }else{
            //See if the node exists or not
                  nObj = grabNode(key,_root);
            
            if(find(key) == null){
                  //The node doesn't exist, so create it
                  parentNode = findParent(key,_root);
                  newNode = new TreeNode(key, item);
                  newNode.setParent(parentNode);
                  Comparable cKey = (Comparable)newNode.getKey();
                  Comparable tKey = (Comparable) parentNode.getKey();
                  if(cKey.compareTo(tKey) < 0){
                        parentNode.setLeft(newNode);
                  }else if(cKey.compareTo(tKey) > 0){
                        parentNode.setRight(newNode);
                  }      
                 //splay(newNode);
                  _size++;
            }else{
                  n = (TreeNode)find(key);
                  //The node does exist, so change its item value
                  n.setItem(item);
                  //splay(n);
            }
            }
      }


      public Object grabNode(Object key, TreeNode x){
            Comparable cKey;
            Comparable tKey;
            Object returnVal = null;
            if(x == null){
                  return null;
            }else{
                  cKey = (Comparable)key;
                  tKey = (Comparable)x.getKey();
              if(cKey.compareTo(tKey) < 0){
              //NODE IS TO THE LEFT OF THE ROOT
                    if(x.getLeft()!=null){
                          return grabNode(key,x.getLeft());
                    }else{
                          return null;
                    }
              }else if(cKey.compareTo(tKey) > 0){
              //NODE IS TO THE RIGHT OF THE ROOT
                    if(x.getRight()!=null){
                          return grabNode(key,x.getRight());
                    }else{
                          return null;
                    }
              }else{
                    //the node exists!!
                    return x.getKey();
              }
            }
      }
0
Comment
Question by:D4Ly
  • 7
  • 7
  • 2
  • +1
18 Comments
 
LVL 86

Expert Comment

by:CEHJ
ID: 12561242
Make sure the object *is* Comparable
0
 
LVL 9

Author Comment

by:D4Ly
ID: 12561246
??
0
 
LVL 86

Expert Comment

by:CEHJ
ID: 12561265
>>
Comparable cKey = (Comparable)newNode.getKey();
              Comparable tKey = (Comparable) parentNode.getKey();
>>

is where you're casting. You need to check that the keys *are* Comparable
0
Concerto's Cloud Advisory Services

Want to avoid the missteps to gaining all the benefits of the cloud? Learn more about the different assessment options from our Cloud Advisory team.

 
LVL 13

Expert Comment

by:petmagdy
ID: 12561280
please do this:
Object object = find(key);
system.out.println("Class type: " + object.getClass().getName());

what does it prints?
0
 
LVL 92

Expert Comment

by:objects
ID: 12561292
post the stack trace for the exception
0
 
LVL 9

Author Comment

by:D4Ly
ID: 12561295
Class type: java.lang.Integer

here's my find():

public Object find(Object key){
            if (_root == null) return null;
            return grabNode(key, _root);
      }
0
 
LVL 9

Author Comment

by:D4Ly
ID: 12561304
java.lang.ClassCastException
at SplayTree.insert(SplayTree.java:159)
      at Question1.insertValues(Question1.java:42)
      at Question1.doIt(Question1.java:19)
      at Question1.main(Question1.java:94)
Exception in thread "main"

I must leave doIt main, and insertValues as-is.
0
 
LVL 13

Expert Comment

by:petmagdy
ID: 12561306
then u can't cast it to TreeNode thats it
0
 
LVL 92

Expert Comment

by:objects
ID: 12561317
And check that find() actually returns a TreeNode as petmagdy  has suggested.
0
 
LVL 9

Author Comment

by:D4Ly
ID: 12561319
ok. this works perfectly fine assuming no duplicates emerge. when a duplicate does emerge (the key is found) the error occurs. so if i can't cast to TreeNode, what is the fix? or a direction toward the fix?
0
 
LVL 13

Expert Comment

by:petmagdy
ID: 12561320
grapNode should return x not x.getInt()
0
 
LVL 13

Accepted Solution

by:
petmagdy earned 1600 total points
ID: 12561327
    public Object grabNode(Object key, TreeNode x){
          Comparable cKey;
          Comparable tKey;
          Object returnVal = null;
          if(x == null){
               return null;
          }else{
               cKey = (Comparable)key;
               tKey = (Comparable)x.getKey();
             if(cKey.compareTo(tKey) < 0){
             //NODE IS TO THE LEFT OF THE ROOT
                  if(x.getLeft()!=null){
                       return grabNode(key,x.getLeft());
                  }else{
                       return null;
                  }
             }else if(cKey.compareTo(tKey) > 0){
             //NODE IS TO THE RIGHT OF THE ROOT
                  if(x.getRight()!=null){
                       return grabNode(key,x.getRight());
                  }else{
                       return null;
                  }
             }else{
                  //the node exists!!
                  return x.getKey();   <--- here is ur problem u should return x;
             }
          }
     }
0
 
LVL 13

Expert Comment

by:petmagdy
ID: 12561333
see the note at this line:

                  return x.getKey();
0
 
LVL 9

Author Comment

by:D4Ly
ID: 12561335
find does not return treenode since it is type object, as specified in the interface implemented in the class find() is found in.

petmagdy, how am i returning x.getInt? x is type TreeNode, so is x.getLeft, x.getRight, and x.getParent
0
 
LVL 13

Expert Comment

by:petmagdy
ID: 12561341
sorry read my last 2 comments
0
 
LVL 9

Author Comment

by:D4Ly
ID: 12561355
sorry...thx for such immediate responses everyone.

petmagdy, it works great now. can you explain why?
0
 
LVL 13

Expert Comment

by:petmagdy
ID: 12561365
grapNode is meant to return the TreeNode itself not the key of the tree node,  u was expecting TreeNode in the return result
0
 
LVL 9

Author Comment

by:D4Ly
ID: 12561373
AH. thx!
0

Featured Post

[Webinar] Database Backup and Recovery

Does your company store data on premises, off site, in the cloud, or a combination of these? If you answered “yes”, you need a data backup recovery plan that fits each and every platform. Watch now as as Percona teaches us how to build agile data backup recovery plan.

Question has a verified solution.

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

Introduction This article is the second of three articles that explain why and how the Experts Exchange QA Team does test automation for our web site. This article covers the basic installation and configuration of the test automation tools used by…
In this post we will learn how to connect and configure Android Device (Smartphone etc.) with Android Studio. After that we will run a simple Hello World Program.
Viewers will learn about if statements in Java and their use The if statement: The condition required to create an if statement: Variations of if statements: An example using if statements:
This tutorial covers a practical example of lazy loading technique and early loading technique in a Singleton Design Pattern.
Suggested Courses

621 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