Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

I am looking into splay trees and I implemented a version. It seems correct. Could someone please let me know if this indeed correct and how to improve it?
I will just show the insert item and splay. It should be enough.
The code is not that big as it seems in the first look.
Briefly, I try to implement the splay tree according to algorithm storing the nodes in the access path in a stack (thePath) as I go up

private Deque<BinaryNode<AnyType>> thePath = new LinkedList<BinaryNode<AnyType>>();  
public enum ZIGZAGTYPE{  
        ZIG_ZAG_LEFT,ZIG_ZAG_RIGHT,
        ZIG_LEFT,ZIG_RIGHT,
        ZIG_ZIG_LEFT,ZIG_ZIG_RIGHT  
}  
public enum CHILDTYPE{LEFT, RIGHT};  

public void insert(AnyType x) {  
        thePath.clear();  
        BinaryNode<AnyType> theRoot = root;  
        if(theRoot == null){  
            theRoot = new BinaryNode<AnyType>(x);  
            root = theRoot;  
            return;  
        }  
        while(theRoot != null){    
            int cmp = x.compareTo(theRoot.value);  
            if(cmp < 0){  
                thePath.push(theRoot);  
                theRoot = theRoot.leftChild;  
            }  
            else{  
                thePath.push(theRoot);  
                theRoot = theRoot.rightChild;  
            }  
        }  
        BinaryNode<AnyType> newNode = new BinaryNode<AnyType>(x);  
        if(thePath.peek().value.compareTo(x) < 0){  
            thePath.peek().rightChild = newNode;  
        }  
        else {  
            thePath.peek().leftChild = newNode;  
        }  
        thePath.push(newNode);  
        splay();  
}

private void splay(){  
        if(thePath.isEmpty()){  
            throw new IllegalStateException();  
        }  
        CHILDTYPE childType;  
        BinaryNode<AnyType> parent;  
        BinaryNode<AnyType> grandParent;  
        BinaryNode<AnyType> current;  
        while(thePath.size() > 1){  
            current = thePath.pop();            
            parent = thePath.pop();  
            ZIGZAGTYPE type ;  
            if(thePath.isEmpty()){  
                //we are at root--> ZIG  
                type = type(null, parent, parent);  
                if(type == ZIG_LEFT){  
                    parent = Rotations.rotateWithLeftChild(parent);                 
                }  
                else{  
                    parent = Rotations.rotateWithRightChild(parent);  
                }  
                thePath.push(parent);   
                root = parent;  
            }  
            else{  
                grandParent = thePath.pop();  
                if(!thePath.isEmpty() && grandParent == thePath.peek().leftChild){  
                    childType = CHILDTYPE.LEFT;    
                }  
                else{      
                    childType = CHILDTYPE.RIGHT;  
                }  
                type = type(grandParent, parent, current);  
                if(type == ZIG_ZAG_LEFT){  
                     //ZIG ZAG
                     grandParent = Rotations.zigzagLeft(grandParent);  

                }  
                else if(type == ZIG_ZAG_RIGHT){  
                     //ZIG ZAG
                     grandParent = Rotations.zigzagRight(grandParent);  

                }               
                else if(type == ZIG_ZIG_RIGHT){  
                     //ZIG ZAG  
                     grandParent = Rotations.zigzigRight(grandParent);       
                }  
                else if(type == ZIG_ZIG_LEFT){  
                     //ZIG ZAG  
                     grandParent = Rotations.zigzigLeft(grandParent);  

                }  
                if(!thePath.isEmpty()){  
                     if(childType == CHILDTYPE.LEFT){  
                         thePath.peek().leftChild = grandParent;  
                     }  
                     else{  
                         thePath.peek().rightChild = grandParent;  
                     }  
                     thePath.push(grandParent);  



                }  
                root = grandParent;      

            }  

        }     
    }    

private ZIGZAGTYPE type(BinaryNode<AnyType> grandParent, BinaryNode<AnyType> parent, BinaryNode<AnyType> x){  
        if(grandParent == null){  
            return parent.leftChild == x?ZIG_LEFT:ZIG_RIGHT;  
        }  
        else if((grandParent.leftChild == parent && parent.rightChild == x)){  
            return ZIG_ZAG_LEFT;  
        }  
        else if((grandParent.rightChild == parent && parent.leftChild == x)){  
            return ZIG_ZAG_RIGHT;  
        }
        else{  
            if((grandParent.leftChild == parent && parent.leftChild == x)){  
                return ZIG_ZIG_LEFT;  
            }  
            else{  
                return ZIG_ZIG_RIGHT;  
            }  
        }  
    }  

    private static class Rotations <AnyType>{  
        public final static<AnyType>  BinaryNode<AnyType> rotateWithLeftChild(BinaryNode<AnyType> r){  
            BinaryNode<AnyType> lc = r.leftChild;  
            r.leftChild = lc.rightChild;  
            lc.rightChild = r;  
            return lc;  
        }  
        public final static<AnyType>  BinaryNode<AnyType> rotateWithRightChild(BinaryNode<AnyType> r){  
            BinaryNode<AnyType> rc = r.rightChild;  
            r.rightChild = rc.leftChild;  
            rc.leftChild = r;  
            return rc;  
        }       


        public final static<AnyType> BinaryNode<AnyType> zigzagLeft(BinaryNode<AnyType> g){  
            BinaryNode<AnyType> p = g.leftChild;  
            g.leftChild = rotateWithRightChild(p);  
            g = rotateWithLeftChild(g);  
            return g;  
        }  

        public final static<AnyType> BinaryNode<AnyType> zigzagRight(BinaryNode<AnyType> g){  
            BinaryNode<AnyType> p = g.rightChild;  
            g.rightChild = rotateWithLeftChild(p);  
            g = rotateWithRightChild(g);  
            return g;  
        }  

        public final static<AnyType> BinaryNode<AnyType> zigzigLeft(BinaryNode<AnyType> g){         
            g = rotateWithLeftChild(g);  
            g = rotateWithLeftChild(g);  
            return g;           
        }  

        public final static<AnyType> BinaryNode<AnyType> zigzigRight(BinaryNode<AnyType> g){            
            g = rotateWithRightChild(g);  
            g = rotateWithRightChild(g);  
            return g;             
        }  
share|improve this question

2 Answers 2

I did not check if the tree is indeed correct, but some comments in your design.

  • rotateWithLeftChild and rotateWithRightChild should be collapsed into some thing like

    public final static<AnyType>  BinaryNode<AnyType> rotateWithChild(BinaryNode<AnyType> r, Direction d){  
      BinaryNode<AnyType> c;
      switch(d) {
      case Left:
        c = r.leftChild;  
        r.leftChild = c.rightChild;  
        c.rightChild = r;  
        return c;  
      case Right:
        c = r.rightChild;  
        r.rightChild = c.leftChild;  
        c.leftChild = r;  
        return c;
      }  
    }     
    
  • zigzagLeft, zigzagRight, zigzagRight, zigzagLeft all should be collapsed into one method that takes an option value, and should do the zig/zag based on it.

    public final static<AnyType> BinaryNode<AnyType> zigzag(BinaryNode<AnyType> g, ZIGZAGTYPE zz){  
      swtich(zz) {
      case ZigzagLeft:
        g.leftChild = rotateWithChild(g.leftChild, Right);  
        return rotateWithChild(g,Left);  
      case ZigzagRight:
        g.rightChild = rotateWithChild(g.rightChild, Left);  
        return rotateWithChild(g,Right);  
      case ZigzigLeft:
        g = rotateWithChild(g,Left);  
        return rotateWithChild(g,Left);  
      case ZigzigRight:
        g = rotateWithChild(g,Right);  
        return rotateWithChild(g,Right);  
    }  
    

The advantage is that, rather than

             if(type == ZIG_ZAG_LEFT){  
                 //ZIG ZAG
                 grandParent = Rotations.zigzagLeft(grandParent);  

             }  
             else if(type == ZIG_ZAG_RIGHT){  
                 //ZIG ZAG
                 grandParent = Rotations.zigzagRight(grandParent);  

             }              
             else if(type == ZIG_ZIG_RIGHT){  
                 //ZIG ZAG  
                 grandParent = Rotations.zigzigRight(grandParent);  

             }  
             else if(type == ZIG_ZIG_LEFT){  
                 //ZIG ZAG  
                 grandParent = Rotations.zigzigLeft(grandParent);  

             } 

You can just call

             grandParent = Rotations.(grandParent, type);  

For the function insert

public void insert(AnyType x) {  
        thePath.clear();  

Avoid temptation to use redundant variables.

        if(root == null){  
            root = new BinaryNode<AnyType>(x);
            return;
        }
        BinaryNode<AnyType> theRoot = root;

Pull out statements that are common in if and else clause Ternaries help to simplify the if conditions when the variation is in a single place.

        while(theRoot != null) {
            thePath.push(theRoot);
            theRoot = x.compareTo(theRoot.value) < 0 ? theRoot.leftChild
                                                     : theRoot.rightChild;
        }

I recommend that rather than using two members leftChild and rightChild, add a 2 element member array child, and refer to each as child[Left] and child[Right]. The advantage is that your code can be considerably simplified.

share|improve this answer

I took a slightly different approach to reviewing this code. I set out to write the missing code and creating a working implementation. Without access to your BinaryNode class I took this one and worked to clean up my SplayTree<AnyType> class that included your code. Here are some changes I made and some notes about how they might help you.

I switched over from public fields like value, leftChild and rightChild to getElement(), setLeft() etc. There are a lot of arguments for and against. Here is one that influenced me, make up your own mind.

You are using a generic type (AnyType), but you are calling compareTo(). You will need to make sure you add extends Comparable<AnyType>> to your SplayTree class and related methods (I'm assuming you know this because it wouldn't compile, so this note is more for others who follow you).

Finally, You can reduce your zigzig and zagzag function in a small way (it's debatable if it's more readable, but it is some tiny amount more efficient, and to me it looks cleaner)

public final static <AnyType extends Comparable<AnyType>> BinaryNode<AnyType> zigzigLeft(BinaryNode<AnyType> g) {
  return rotateWithLeftChild(rotateWithLeftChild(g));
}

I like rahul's idea that you can simplify the left/right methods by storing the child nodes in an array and passing a LEFT or RIGHT index.

I'm going to have fun implementing a find() method and checking out if this code is correct.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.