?
Solved

Splay part 3

Posted on 2004-11-13
39
Medium Priority
?
306 Views
Last Modified: 2008-01-09
Alright, so now my insert and find methods work, with the splay method call commented out. Once allowing the inserted or found node to splay itself to the top of the tree, I run into an error.

My rotateLeft and rotateRight methods are my attempts to translate the diagrams from this link objects sent me under section 2, and my splay() is set up to do the proper combinations of rotations depending on the three cases described under section 2 of the same link.

The link: http://www.cs.caltech.edu/courses/cs134/cs134b/2002/labs/lab1/lab1.pdf

Can you guys suggest some things  to look over/fix/improve upon in my splay(), rotateLeft(), rotateRight()?

The code.

private void splay(TreeNode x){            
             if((x.getParent() != null) && (x.getParent().getParent() == null)){
                   rotateRight(x);
             }else if(((x.getParent() != null) && (x.getParent().getParent() != null))){
                   if((x.getParent().getLeft() == x) && (x.getParent().getParent().getLeft() == x.getParent())){
                         rotateLeft(x);
                         rotateRight(x);      
                   }else if((x.getParent().getRight() == x) && (x.getParent().getParent().getRight() == x.getParent())){
                         rotateLeft(x);
                         rotateRight(x);      
                   }else if((x.getParent().getLeft() == x) && (x.getParent().getParent().getRight() == x.getParent())){
                         rotateRight(x);
                         rotateRight(x);
                   }else if((x.getParent().getRight() == x) && (x.getParent().getParent().getLeft() == x.getParent())){
                         rotateRight(x);
                         rotateRight(x);
                   }
             }
             if(x != _root){
                   splay(x);
             }
            
      }


      /**
       * Rotates this node with the left child, moving the left child
       * closer to the root, possibly making it the root.
       * @param y parent node to rotate around
       */
      private void rotateRight(TreeNode y){                  
            TreeNode x = y.getLeft();
            x.getParent().setLeft(x.getRight());
            x.getRight().setParent(x.getParent());
            x.setRight(x.getParent());
            x.getParent().setParent(x);
            x.setParent(x.getParent().getParent());
            if(x.getRight() == x.getParent().getLeft()){
                  x.getParent().setLeft(x);
            }else if(x.getRight() == x.getParent().getRight()){
                  x.getParent().setRight(x);
            }
            if(x.getParent() == null){
                  _root = x;
            }
      }
      


      /**
       * Rotates this node with the right child, moving the right child
       * closer to the root, possibly making it the root.
       * @param p parent node to rotate around.
       */
      private void rotateLeft(TreeNode y){
            TreeNode x = y;
            TreeNode temp;
            x.getRight().setParent(x.getParent());
            x.getRight().getLeft().setParent(x);
            x.setParent(x.getRight());
            temp = x.getRight().getLeft();
            x.getRight().setLeft(x);
            x.setRight(temp);
            if(x.getParent() == x.getParent().getParent().getLeft()){
                  x.getParent().getParent().setLeft(x.getParent());
            }else if(x.getParent() == x.getParent().getParent().getRight()){
                  x.getParent().getParent().setRight(x.getParent());
            }
            if(x.getParent().getParent() == null){
                  _root = x.getParent();
            }
      }
0
Comment
Question by:D4Ly
  • 21
  • 18
39 Comments
 
LVL 13

Expert Comment

by:petmagdy
ID: 12575179
What is the error u get? is it StackOverFlow? not sure but seems to me the problem with the slay is that it will recurse for ever, the condition to stop recursing is defintly wrong which is:

        >>   if(x != _root)

shouldn't it be:
if (x.equals(_root))
?
does ur TreeNode implements equal() method?
0
 
LVL 13

Expert Comment

by:petmagdy
ID: 12575202
by the way in my last comment:
>> if (x.equals(_root))
I mean
if (x.equals(_root) == false)

also all ur if conditions r using == on TreeNode this is completely wrong ur TreeNode must implement
public boolean equals(Object compared)
{
 //return true if as ur logic is equal
}
0
 
LVL 13

Expert Comment

by:petmagdy
ID: 12575236
and then all the (==) in the all if conditions should be relaced with equals()
0
Concerto Cloud for Software Providers & ISVs

Can Concerto Cloud Services help you focus on evolving your application offerings, while delivering the best cloud experience to your customers? From DevOps to revenue models and customer support, the answer is yes!

Learn how Concerto can help you.

 
LVL 9

Author Comment

by:D4Ly
ID: 12575244
hmm, no my TreeNode does not have an equal() method implementation.

As far as the error received:
java.lang.NullPointerException
      at SplayTree.rotateRight(SplayTree.java:86)
      at SplayTree.splay(SplayTree.java:32)
      at SplayTree.insert(SplayTree.java:154)
      at Question1.insertValues(Question1.java:35)
      at Question1.doIt(Question1.java:19)
      at Question1.main(Question1.java:94)
Exception in thread "main"


this rotateRight line is:
x.getParent().setLeft(x.getRight());

This occurs first when treenode with value 1 is inserted and the splay method is called. (the first time the splay is called).

I don't understand the reason for the equals method in terms of how it differs from ==. (I'm quite the noob to java).

The error makes me believe the way i am implementing the pointer changes for my rotations is incorrect.

0
 
LVL 9

Author Comment

by:D4Ly
ID: 12575252
this may be a possible alternative to the lack of my equals() being present. in my splay class, i do have this:
Comparator _c;
0
 
LVL 13

Expert Comment

by:petmagdy
ID: 12575281
>> x.getParent().setLeft(x.getRight());

this line may cause 2 possible cases for null pointer exception if x.getParent() returns null or x.getRight() returns null, u must check for nulls first

>>this may be a possible alternative to the lack of my equals() being present. in my splay class, i do have this:
>>Comparator _c;

note sure what u mean please implement equals in ur tree node and replace == in ur if conditions with like:
 if(x.equals(something))
0
 
LVL 9

Author Comment

by:D4Ly
ID: 12575286
how do i implement equals?
public boolean equals(Object compared)
{
 //return true if as ur logic is equal
}
what logic am i using here?
0
 
LVL 13

Expert Comment

by:petmagdy
ID: 12575312
the logic to ensure that the TreeNodes u r comparing between are the same, like comparing the ID the important thing is to compare something unique per node, please refer to Object.equals()
0
 
LVL 9

Author Comment

by:D4Ly
ID: 12575364
public boolean equals(Object toCompare){
            return this == toCompare;
      }
isn't this the same thing?
0
 
LVL 13

Expert Comment

by:petmagdy
ID: 12575373
could u please post ur TreeNode class
0
 
LVL 9

Author Comment

by:D4Ly
ID: 12575379
yeah, here it is with my equals as above.



/**
 *
 */
public class TreeNode {
      
      TreeNode _parent;
      TreeNode _left;
      TreeNode _right;
      Object _item;
      Object _key;
      
      public TreeNode(Object key, Object item){
            _key=key;
            _item=item;
            _parent=null;
            _left=null;
            _right=null;
      }
      
      /**
       * @return Returns the left child.
       */
      public TreeNode getLeft() {
            return _left;
      }
      /**
       * @param left The left child to set.
       */
      public void setLeft(TreeNode left) {
            this._left = left;
      }
      /**
       * @return Returns the parent node.
       */
      public TreeNode getParent() {
            return _parent;
      }
      /**
       * @param parent The parent to set.
       */
      public void setParent(TreeNode parent) {
            this._parent = parent;
      }
      /**
       * @return Returns the right child.
       */
      public TreeNode getRight() {
            return _right;
      }
      /**
       * @param right The right child to set.
       */
      public void setRight(TreeNode right) {
            this._right = right;
      }
      
      
      
      /**
       * @return Returns the item.
       */
      public Object getItem() {
            return _item;
      }
      /**
       * @param item The item to set.
       */
      public void setItem(Object item) {
            this._item = item;
      }
      /**
       * @return Returns the key.
       */
      public Object getKey() {
            return _key;
      }
      /**
       * @param key The key to set.
       */
      public void setKey(Object key) {
            this._key = key;
      }
      
      public boolean equals(Object toCompare){
            return this == toCompare;
      }
}
0
 
LVL 13

Expert Comment

by:petmagdy
ID: 12575418
k tell me D4Ly ur TreeNode have 5 member fields what combination of those fields represents the tree node unique identification along the whole tree? which means this combination of fields values can't be repeated for 2 nodes
0
 
LVL 9

Author Comment

by:D4Ly
ID: 12575426
the key cannot be repeated.
the parent, left, right are pointers to the possible children and parent of this splay tree

the item is the value stored in that node. the tree is ordered by its key.
0
 
LVL 13

Expert Comment

by:petmagdy
ID: 12575436
then ur equal method is simply:

public boolean equals(Object comparedObj)
{
 TreeNode comparedNode = (TreeNode) comparedObj;
 return _key.equals(comparedNode.getKey());
}

easy :-)

now apply this all over ur code instead of "=="
0
 
LVL 9

Author Comment

by:D4Ly
ID: 12575442
yup...i realized this as soon as i submitted. one sec. i'll see what I've got.
0
 
LVL 13

Expert Comment

by:petmagdy
ID: 12575453
D4Ly
one important correction correction
public boolean equals(Object comparedObj)
{
  if(comparedObj == null)
  {
    return false;
  }
 TreeNode comparedNode = (TreeNode) comparedObj;
 return _key.equals(comparedNode.getKey());
}
0
 
LVL 9

Author Comment

by:D4Ly
ID: 12576031
sry for the late response. I had to rip my lan apart a home to install my dad's new computer (the server).  I found this error, and wondered whether to put the .equals(null) or just leave == null...in this case I assume they are interchangeable for null values.  In any event, i made this change already.

I still receive the same nullPointerException however.

x.getParent().setLeft(x.getRight());

see this line in the original post. its the 2nd line of the rotate right method.  My tree has values 0-10 inserted incrementally. The 0 goes in fine, since no splay needs to be called as it is the first value being inserted into an empty tree.  The 1 (the next value inserted) does not splay properly when the splay method is called. Instead this nullPointerException shows up.

I think the problem is the interpretation of the rotation methods I came up with from the diagrams on the link referenced in the original post in section #2.

Though I cannot figure out how I am going wrong.
0
 
LVL 9

Author Comment

by:D4Ly
ID: 12576055
Alright, so I think its time for a sidenote.

I'm a 3rd semester CS major at a state university. Thus far, I have taken Intro to CS (basic C++) which was an absolute breeze, Intro to OOP (also equally a breeze). Now I am taking Discrete Math (again, love it), and finally this course...Intro to algorithms and datastructures (Java based).  Before this semester I have never touched java.  I don't really struggle with the concept of OOP, which the course greatly focuses on, as most of the q's i post in EE are little slaps in the face screaming "WHY DIDN"T YOU SEE THAT EARLIER???".  However, when it comes to things like this whole == versus equals(), we are never taught this....i assume I'm just expected to know it...but how could I? That's why I'm in college, to learn these differences...among other things.  Now, when it comes to 350+ lines of code written at once with no opportunity to debug until all this is written, I become a bit overwhelmed with finding out exactly what is happening wrong.

I love CS. Its the one thing that has stayed a constant interest for me longer than anything else. I have always seen myself doing this for a living, and know I CAN do this for a living, and do it WELL. My problem is that I don't know whether my problem is my teacher, my school, or me...and i'd rather not assume its' me.

Can you reflect/relate to this in ANY way or offer advice?
0
 
LVL 13

Expert Comment

by:petmagdy
ID: 12576102
I think u rushed into writing rather complex code like slay tries and staff in a short time, u didn't took ur time first to go deep into java core, also U have written a huge amout of code in one shot, u supposed to get first aquanted with an IDE like eclipse or netbeans and how to neatly and gradually build, trace and debug ur code
any way u r still in the beginning and trying to learn very quickly
For C or Java issue, well it depends on what u want to do and like the tools used to build a rocket is defferent than the tools to build a computer, the tools to build an OS is different than for building a portal for example, so do u plan to build an OS or a portal? ;-)
0
 
LVL 9

Author Comment

by:D4Ly
ID: 12576404
That's what bad teaching will do I suppose. I have no choice but to code these large chunks so quickly.

how about this earlier post:
sry for the late response. I had to rip my lan apart a home to install my dad's new computer (the server).  I found this error, and wondered whether to put the .equals(null) or just leave == null...in this case I assume they are interchangeable for null values.  In any event, i made this change already.

I still receive the same nullPointerException however.

x.getParent().setLeft(x.getRight());

see this line in the original post. its the 2nd line of the rotate right method.  My tree has values 0-10 inserted incrementally. The 0 goes in fine, since no splay needs to be called as it is the first value being inserted into an empty tree.  The 1 (the next value inserted) does not splay properly when the splay method is called. Instead this nullPointerException shows up.

I think the problem is the interpretation of the rotation methods I came up with from the diagrams on the link referenced in the original post in section #2.

Though I cannot figure out how I am going wrong.
0
 
LVL 9

Author Comment

by:D4Ly
ID: 12576435
Now that I have added .equals to all places where == appears for type TreeNode and type Object, I am left with an initial error here:
      /**
       * @param key The key to search for
       * @param x The current TreeNode being compared
       */
      public Object grabNode(Object key, TreeNode x){
            Comparable cKey;
            Comparable tKey;
            Object returnVal = null;
            if(x.equals(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().equals(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().equals(null))){                        //ERROR HERE nullPointerException
                          return grabNode(key,x.getRight());
                    }else{
                          return null;
                    }
              }else{
                    //the node exists!!
                    return x;
              }
            }
      }

When trying to traverse the tree to find the node, a null value is reached as 0 is the only element in the tree, at the root.

0
 \
  x

x is where the exception occurs, as no node exists here. what should happen is this null is returned telling the insert function the node does not already exist, and to go ahead and insert a new node in x's position.  Have I set up my null incorrectly?
0
 
LVL 13

Expert Comment

by:petmagdy
ID: 12577442
just one thing, don't use Equal with null
>>         if(x.equals(null)){
 
if x is null it will through NullPointerException, change it to be:
 if(x==null){

so I will just update the rule use equal instead of == expect when u compare to an explicit null :-)
for such experission like:
 >>                 if(!(x.getRight().equals(null))){                        //ERROR HERE nullPointerException
it should be:
if(x.getRight() != null ) {

for:

>> x.getParent().setLeft(x.getRight());
this statment before to be called must pass throught 3 checks:
1- x is not null
2- x.getParent() is not null
3- x.getRight() is not null

 
 
0
 
LVL 13

Expert Comment

by:petmagdy
ID: 12577455
for:

>> x.getParent().setLeft(x.getRight());
u may consider doing this:
if(x != null)
{
  if(x.getParent() != null && x.getRight() != null)
 {
   x.getParent().setLeft(x.getRight());
 }
}
0
 
LVL 9

Author Comment

by:D4Ly
ID: 12579099
putting these println's in i find the nullPointerException I am getting as of now comes after 0 is inserted and then 1 is inserted. once 1 is inserted the splay is called for the first time, and a rotateRight is called. In this case, I know that for this line:
 x.getParent().setLeft(x.getRight());
getParent must exist. however, i also know for this case that the tree looks like this:
0
 \
  1
   \
    null

so x (being 1), does have NO right child to get. My hope here is that null would be returned, setting the tree to this
    1
   / \
  0   null

which would be a proper splay.

does this make sense? in other words, i don't care if getRight exists, since if it doesn't i want null.

      private void splay(TreeNode x){      
             if((x.getParent() != null) && (x.getParent().getParent() == null)){
                   System.out.println("RotateRight");
                   rotateRight(x);
             }else if(((x.getParent() != null)) && (x.getParent().getParent() != null)){
                   if((x.getParent().getLeft().equals(x)) && (x.getParent().getParent().getLeft().equals(x.getParent()))){
                         System.out.println("rotateLeft, RotateRight");
                         rotateLeft(x);
                         rotateRight(x);      
                   }else if((x.getParent().getRight().equals(x)) && (x.getParent().getParent().getRight().equals(x.getParent()))){
                         System.out.println("rotateLeft, RotateRight");
                         rotateLeft(x);
                         rotateRight(x);      
                   }else if((x.getParent().getLeft().equals(x)) && (x.getParent().getParent().getRight().equals(x.getParent()))){
                         System.out.println("rotateRight, RotateRight");
                         rotateRight(x);
                         rotateRight(x);
                   }else if((x.getParent().getRight().equals(x)) && (x.getParent().getParent().getLeft().equals(x.getParent()))){
                         System.out.println("rotateRight, RotateRight");
                         rotateRight(x);
                         rotateRight(x);
                   }
             }
             if(x != _root){
                   splay(x);
             }
      }
0
 
LVL 13

Expert Comment

by:petmagdy
ID: 12579137
D4LY
which line now is causing Null pointer exception? could u please get the line number from the stack trace
Also with such complex code u need to learn to debug :)
0
 
LVL 13

Accepted Solution

by:
petmagdy earned 2000 total points
ID: 12579169
also I would suggest some methods to be added to TreeNode that will make ur life much easier those are:

public boolean hasParent()
{
  return ( _parent != null );
}

public boolean hasGrandParent() {
 if(hasParent())
 {
     return ( _parent.getParent() != null );
 }
 return false;
}

in the same way create methods hasLeft(), hasRight() and maybe hasItem()

now apply those on the ugly look slay function believe me it will make a very big difference!! and the function will be more reliable against Null pointer exceptions
0
 
LVL 9

Author Comment

by:D4Ly
ID: 12579174
petmagdy-

without your change the same line is still the source of the error.

with your code change:
if(x != null)
            {
              if(x.getParent() != null && x.getRight() != null)
             {
               x.getParent().setLeft(x.getRight());
             }
            }
            
            //x.getParent().setLeft(x.getRight());
            x.getRight().setParent(x.getParent());  //NEW SOURCE OF ERRER (ie, the next line)

but check it out....if x.getRight() IS null (the treeNode doesn't exist), i still want to let x.getParent().setLeft()  BE null. I want it to point to nothing. So then for your suggested change, i would want to do something like this instead:

if(x != null){
        if(x.getParent() != null){
              if(x.getRight() != null){
                    x.getParent().setLeft(x.getRight());
              }else if(x.getRight() == null){
                    x.getParent.setLeft(null);
              }
       }
}

I know I should know how to debug for code like this.  I'm learn more about debugging with every answer tho ;p.
0
 
LVL 13

Expert Comment

by:petmagdy
ID: 12579183
then make it like this:
if(x != null)
          {
            if(x.getParent() != null)
           {
             x.getParent().setLeft(x.getRight());
           }
          }
 
also please apply the methods i gave to u last comment so ur code to be more readable and reliable and I can be able more to help u
0
 
LVL 9

Author Comment

by:D4Ly
ID: 12579184
ok, that sounds like a plan.

THEN, your change would look like this:
                 if(x != null){
                    if(x.hasParent()){
                          if(x.hasRight()){
                                x.getParent().setLeft(x.getRight());
                          }else{
                                x.getParent().setLeft(null);
                          }
                   }
            }
0
 
LVL 9

Author Comment

by:D4Ly
ID: 12579189
and if x ==null, its the root, so i'm done.
0
 
LVL 13

Expert Comment

by:petmagdy
ID: 12579193
read my last 2 comments man :-)
0
 
LVL 9

Author Comment

by:D4Ly
ID: 12579202
yeah, i assume you're responding to the //NEW SOURCE OF ERROR post. I've made some improvements and am realizing a lot now.  I'll post back once I've done some major work here.
0
 
LVL 9

Author Comment

by:D4Ly
ID: 12579307
k, i'm now left with this as my rotateRight():

      private void rotateRight(TreeNode y){                  
            TreeNode x = y.getLeft();
             if(x != null){
            if(x.hasParent()){
                 if(x.hasRight()){
                      x.getParent().setLeft(x.getRight());
                      x.getRight().setParent(x.getParent());
                 }else{
                      x.getParent().setLeft(null);
                 }
                 x.setRight(x.getParent());
                 x.getParent().setParent(x);
                 if(x.hasGrandParent()){
                       x.setParent(x.getGrandParent());
                 }else{
                       x.setParent(null);
                 }
                 if(x.hasParent()){
                                   if(x.getRight() == x.getParent().getLeft()){
                                         x.getParent().setLeft(x);
                                   }else if(x.getRight().equals(x.getParent().getRight())){
                                         x.getParent().setRight(x);
                                   }
                 }
           }else{
                       _root = x;
           }
     }

much simpler. and here's my splay:

private void splay(TreeNode x){                        
             if((x.getParent() != null) && (x.getParent().getParent() == null)){
                   System.out.println("RotateRight");
                   rotateRight(x);
             }else if(x.hasParent() && x.hasGrandParent()){
                   if((x.getParent().getLeft().equals(x)) && (x.getGrandParent().getLeft().equals(x.getParent()))){
                         System.out.println("rotateLeft, RotateRight");
                         rotateLeft(x);
                         rotateRight(x);      
                   }else if((x.getParent().getRight().equals(x)) && (x.getGrandParent().getRight().equals(x.getParent()))){
                         System.out.println("rotateLeft, RotateRight");
                         rotateLeft(x);
                         rotateRight(x);      
                   }else if((x.getParent().getLeft().equals(x)) && (x.getGrandParent().getRight().equals(x.getParent()))){
                         System.out.println("rotateRight, RotateRight");
                         rotateRight(x);
                         rotateRight(x);
                   }else if((x.getParent().getRight().equals(x)) && (x.getGrandParent().getLeft().equals(x.getParent()))){
                         System.out.println("rotateRight, RotateRight");
                         rotateRight(x);
                         rotateRight(x);
                   }
             }
             if(x != _root){
                   splay(x);
             }
}

thanks very much for helping to simplify this.

Now, the program runs without error on inserting 1, but runs endlessly (1 must never make it to the root). I will attempt to DEBUG on my OWN!!!! ;p we'll see how far I get tho lol. Obviously I have already cornered my error to the rotateRight method.

Petmagdy, if there was a way to give 30,000pts, I would be on track to doing so.
0
 
LVL 13

Expert Comment

by:petmagdy
ID: 12579322
thanks u r wecome
i think it is going for ever for this:

           if(x != _root){
                splay(x);
           }

this is != that should be equals()
0
 
LVL 9

Author Comment

by:D4Ly
ID: 12580001
yes, this works...but why?

I want the splay(x) to happen while x is NOT the root. so that once x IS the root (x == _root),  the splay will stop.  Either way, your a genious and this is fine...but i would love the opportunity to learn more.
0
 
LVL 9

Author Comment

by:D4Ly
ID: 12580103
Okay, so I think I am really starting to understand how to approach this all...the cleaning of the getLeftgetRightgetParentblablabla helped a GREAT deal.

I think one of my last few questions is:
So inserting 1 runs for the first case just fine. and I must now fix the rotateLeft similar to how you helped with the rotateRight, and hopefully I can do this on my own.
0
 \
  1

insert 2 gives
    1
   /  \
  0    2
now splay(2)


here is my printed tree in this fashion NODEKEY: LEFTCHILDKEY, RIGHTCHILDKEY.
0: null, 1
1: null, null

the tree SHOULD look like this
0: null, null
1: 0, null

in other words, the rotate right was called, but did nothing, since x = y.getLeft in the rotateRight() method yields null, and the method says if x == null, set it to be the root.

Again, my rotateRight comes from the diagram on this link. http://www.cs.caltech.edu/courses/cs134/cs134b/2002/labs/lab1/lab1.pdf


      private void rotateRight(TreeNode y){                  
            TreeNode x = y.getLeft();
             if(x != null){
            if(x.hasParent()){
                 if(x.hasRight()){
                      x.getParent().setLeft(x.getRight());
                      x.getRight().setParent(x.getParent());
                 }else{
                      x.getParent().setLeft(null);
                 }
                 x.setRight(x.getParent());
                 x.getParent().setParent(x);
                 if(x.hasGrandParent()){
                       x.setParent(x.getGrandParent());
                 }else{
                       x.setParent(null);
                 }
                 if(x.hasParent()){
                                   if(x.getRight() == x.getParent().getLeft()){
                                         x.getParent().setLeft(x);
                                   }else if(x.getRight().equals(x.getParent().getRight())){
                                         x.getParent().setRight(x);
                                   }
                 }
           }else{
                       _root = x;
           }
     }

here's another description for what i must accomplish with my splay, rotateLeft and rotateRight.

To splay the node X:
1. If X is root, do nothing.
2. If X has no grandparent (i.e., the parent of X is root), rotate X about
its parent. This will make X be root. (ZIG operation)
3. If X has a grandparent:
(a) If X and its parent are both left-children or both right-children (ZIG-ZIG)
rotate the parent about the grand-parent, then rotate X about its parent.
(b) If X and its parent are opposite-type children (one is left, the other
is right - ZIG-ZAG) rotate X about its parent, then rotate X about its new
parent (i.e., its former grandparent).

and the more i look things over, i think i'm realizing I might not be accomplishing this.
0
 
LVL 13

Expert Comment

by:petmagdy
ID: 12581218
yes the reason that the expression:

          if(x != _root){
                splay(x);
           }

will be always true because u r comparing references not objects, hence it must be:

         if(x.equals(_root) == false){
                splay(x);
           }
0
 
LVL 9

Author Comment

by:D4Ly
ID: 12584543
Alright, I'm gonna do some work to all of this.

I think I need to change my rotate right and left methods.

Thanks so far for all your help. The points are yours, I just can't close the question yet.
0
 
LVL 9

Author Comment

by:D4Ly
ID: 12633941
So, I've got my tree working petmagdy, thanks to your help...here's your points!! ;p
0

Featured Post

[Webinar] Cloud and Mobile-First Strategy

Maybe you’ve fully adopted the cloud since the beginning. Or maybe you started with on-prem resources but are pursuing a “cloud and mobile first” strategy. Getting to that end state has its challenges. Discover how to build out a 100% cloud and mobile IT strategy in this webinar.

Question has a verified solution.

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

An old method to applying the Singleton pattern in your Java code is to check if a static instance, defined in the same class that needs to be instantiated once and only once, is null and then create a new instance; otherwise, the pre-existing insta…
Java Flight Recorder and Java Mission Control together create a complete tool chain to continuously collect low level and detailed runtime information enabling after-the-fact incident analysis. Java Flight Recorder is a profiling and event collectio…
Viewers learn about the third conditional statement “else if” and use it in an example program. Then additional information about conditional statements is provided, covering the topic thoroughly. Viewers learn about the third conditional statement …
Viewers learn about the “for” loop and how it works in Java. By comparing it to the while loop learned before, viewers can make the transition easily. You will learn about the formatting of the for loop as we write a program that prints even numbers…
Suggested Courses
Course of the Month13 days, 20 hours left to enroll

807 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