java - Implementing splay() method for Binary Search Tree -

i trying implement splay(node x) method binary search tree. have leftrotation(node x) , rightrotation(node x) methods implemented correctly (atleast, think are...), when try implement them in splay(node x) method, calls in infinite loop. now, know why it's doing that, can't seem figure out how fix it.

here leftrotation(node x) method:

public void leftrotation(node<e> x) {     if (x.getrightchild() == null) {         return;     }      node<e> y = x.getrightchild();     x.setrightchild(y.getleftchild());      if (y.getleftchild() != null) {         y.getleftchild().setparent(x);     }      y.setparent(x.getparent());      if (x.getparent() == null) {         root = y;     } else {         if (x == x.getparent().getleftchild()) {             x.getparent().setleftchild(y);         } else {             x.getparent().setrightchild(y);         }     }      y.setleftchild(x);     x.setparent(y); } 

here's rightrotation(node x) method:

public void rightrotation(node<e> x) {     if (x.getleftchild() == null) {         return;     }      node<e> y = x.getleftchild();     x.setrightchild(y.getrightchild());      if (y.getrightchild() != null) {         y.getrightchild().setparent(x);     }      y.setparent(x.getparent());      if (x.getparent() == null) {         root = y;     } else {         if (x == x.getparent().getrightchild()) {             x.getparent().setrightchild(y);         } else {             x.getparent().setleftchild(y);         }     }      x.setrightchild(x);     x.setparent(y); } 

and here's splay(node x) method:

public void splay(node<e> x) {     while (x.getparent() != null) {         if (x.isleftchild && x.getparent().isleftchild) {             this.rightrotation(x.getparent());             this.rightrotation(x);         } else if (x.isrightchild && x.getparent().isrightchild) {             this.leftrotation(x.getparent());             this.leftrotation(x);         } else if (x.isleftchild && x.getparent().isrightchild) {             this.rightrotation(x);             this.leftrotation(x);         } else if (x.isrightchild() && x.getparent().isleftchild()) {             this.leftrotation(x);             this.rightrotation(x);         } else if (x.isleftchild && x.getparent() == root) {             this.rightrotation(x);         } else if (x.isrightchild && x.getparent() == root) {             this.leftrotation(x);         }     } } 

any ideas on how fix infinite loop? seems not breaking out of while(x.getparent() != null) statement in splay(node x) method, when went through code using debugger, properties of node seemed changing, don't know it's going wrong?

setleftchild(node leftchild) method:

public void setleftchild(node<e> leftchild) {         this.leftchild = leftchild;          if (leftchild != null) {             leftchild.setisrightchild(true);             leftchild.setparent(this);         }     } 

apart mistakes/bad things pointed out in code, here biggest one, in rightrotation :

x.setrightchild(x); 

this creates cycle in tree, hence infinite loop. should have unit tested methods. 1 other major error in code if - else if instructions not have else there might cases nothing happens during iteration... hence infinite loop. it's not case here because considered cases (actually, considered more, , 2 last ones never executed because 4 first cases cover every possible case) general remark, dangerous code way.

here code of own implementation of these methods, deem cleaner :

public class binarytree<t extends comparable<t>> {     private node<t> root;      public void rebalance(node<t> node) {         while (!node.isroot()) rotation(node.getparent(), node.getchildkind().opposite());     }      private void rotation(node<t> node, side side) {         if (node.getchild(side.opposite()) == null) return;          node<t> sidechild = node.getchild(side.opposite());         node.setchild(sidechild.getchild(side), side.opposite());          if (node.getparent() == null) setroot(sidechild);         else                          node.getparent().setchild(sidechild, node.getchildkind());          sidechild.setchild(node, side);     }      private void setroot(node<t> root) {         this.root = root;         if (root != null) root.setroot();     }      private static enum side {          left, right;          public side opposite() { return == left ? right : left; }     }      private static class node<t extends comparable<t>> {         private t value;         private node<t> left, right, parent;          public node(t value) { this(value, null, null, null); }           public node(t value, node<t> left, node<t> right, node<t> parent) {             setvalue (value );             setleft  (left  );             setright (right );             setparent(parent);         }          public node<t> setleft(node<t> left) {             this.left = left;             if (left != null) left.parent = this;             return this;         }          public node<t> setright(node<t> right) {             this.right = right;             if (right != null) right.parent = this;             return this;         }          public node<t> setchild(node<t> child, side side) { return side == side.left ? setleft(child) : setright(child); }          public node<t> setroot() { return setparent(null); }          private node<t> setparent(node<t> parent) {             this.parent = parent;             return this;         }          public node<t> setvalue(t value) {             this.value = notnull(value);             return this;         }          public boolean isroot() { return parent == null; }          public boolean isleftchild () { return isroot() || getparent().getvalue().compareto(getvalue()) > 0; }         public boolean isrightchild() { return isroot() || !isleftchild()                                  ; }          public node<t> getchild(side side) { return side == side.left ? getleft() : getright(); }          public side getchildkind() {              check.isfalse(isroot(), "this method not defined on root nodes");             return isleftchild() ? side.left : side.right;          }          public t       getvalue () { return value ; }         public node<t> getleft  () { return left  ; }         public node<t> getright () { return right ; }         public node<t> getparent() { return parent; }     } } 

note : tree not optimally rebalanced. did out of head check @ wikipedia see say, did not apply right algorithm, works pretty fine expect in pathologic cases.