Splay Tree insert() issue

So, Ive completed my splay tree implementation and began debugging, and I've come across a problem. I have removed all splay() requests from my insert, and am inserting 10 values, 1-10. The tree should look like this:

1
 \
  2
   \
    3
     \
      4
       \
        5
         \
          6
           ...... on to 10

The problem is that every newNode created references the root as its parent, instead of moving all the way right (this movement is done in the findParent() method)
As far as i can tell, the setRight() and setParent() for the newNode and its parentNode in the insert() are fine, and the problem lies in the returning of the parent node from my findParent() method. What happens is the return x; inside the if statements of findParent() eventually find the proper parent node to reference through recursion, but I can't figure out where my recursive logic goes wrong, because it also sometime uses the default return x; outside of the conditionals, returning the root.  I can't figure out where my recursive logic is messed up.

Here's the insert method:
public void insert(Object key, Object item){
            TreeNode parentNode, n, newNode;
            parentNode = null;
            if (isEmpty()) {
                _root = new TreeNode(key, item);
            }else{
            //See if the node exists or not
            n = (TreeNode)grabNode(key,_root);
            
            if(n == null){
                  //The node doesn't exist, so create it
                        //Find the node that the newnode should be the child of prior to splaying (code for this below)
                  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);
                  }
                  print();
                  System.out.println("----------------------");
                  //splay(newNode);
            }else{
                  //The node does exist, so change its item value
                  n.setItem(item);
                  //splay(n);
            }
            }
            _size++;
      }

public TreeNode findParent(Object key, TreeNode x){
            Comparable cKey = (Comparable)key;
            Comparable tKey = (Comparable) x.getKey();
                  if(cKey.compareTo(tKey) < 0){
              //Place somewhere to the left of this node
                        if(x.getLeft() != null){
                              findParent(key,x.getLeft());
                        }else{
                              return x;
                        }
              }else{
              //Place somewhere to the right of this node
                    if(x.getRight()!=null){
                          findParent(key,x.getRight());
                    }else{
                          return x;
                    }
              }
          return x;
      }
      public Object grabNode(Object key, TreeNode x){
            Comparable cKey;
            Comparable tKey;
            Object returnVal = null;
            if(x != null){
                  cKey = (Comparable)key;
                  tKey = (Comparable)x.getKey();
              if(cKey.compareTo(tKey) < 0){
              //NODE IS TO THE LEFT OF THE ROOT
                    grabNode(key,x.getLeft());
              }else if(cKey.compareTo(tKey) > 0){
              //NODE IS TO THE RIGHT OF THE ROOT
                    grabNode(key,x.getRight());
              }else if(cKey.compareTo(tKey) == 0){
                    //the node exists!!
                    returnVal = tKey;
              }
            }
              return returnVal;
      }
LVL 9
D4LyAsked:
Who is Participating?
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

GuntCommented:
First (and aside from the question), you are always incrementing the tree size in the insert method, even if the node existed and you just updated it's value. The size should only be increased if the node didn't exists and you inserted it.

The problem in your recursive algorithm, is that you never return the return value from the recursive call.
The idea is:

public TreeNode findParent(Object key, TreeNode x){
          Comparable cKey = (Comparable)key;
          Comparable tKey = (Comparable) x.getKey();
               if(cKey.compareTo(tKey) < 0){
             //Place somewhere to the left of this node
                    if(x.getLeft() != null){
                         return findParent(key,x.getLeft()); <-------- HERE
                    }else{
                         return x;
                    }
             }else{
             //Place somewhere to the right of this node
                  if(x.getRight()!=null){
                       return findParent(key,x.getRight()); <------- HERE
                  }else{
                       return x;
                  }
             }
//         return x; <------- this commented out
     }

Check the lines marked with HERE. Recursion in this case is about delegation. If the node is lesser than the current node but it doesn't have place, then the parent node is the parent node from that.
I think I messed up thing with that last sentence :P

The idea is: If you make the recursive call and do nothing with what it returns, what's the point of making the call?.

grabNode has a similar problem.

Try the Tree with these ideas.
0

Experts Exchange Solution brought to you by

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Start your 7-day free trial
D4LyAuthor Commented:
boooo me! so silly.  Gunt, thanks very much. your a champion. works wonderfully. Here's 500 pts.  PS, where does the name Gunt come from, if you don't mind my asking.
0
GuntCommented:
My pleasure.

Gunt is just half of my name :P
0
D4LyAuthor Commented:
:)
0
It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today
Java

From novice to tech pro — start learning today.

Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.