[Okta Webinar] Learn how to a build a cloud-first strategyRegister Now

x
  • Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 340
  • Last Modified:

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;
      }
0
D4Ly
Asked:
D4Ly
  • 2
  • 2
1 Solution
 
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
 
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

Featured Post

Independent Software Vendors: 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!

  • 2
  • 2
Tackle projects and never again get stuck behind a technical roadblock.
Join Now