Null pointer exception in bottom up splay tree splaying

Question

I am trying to do a bottom up splay tree in java. But somehow, I would get a null-pointer exception in my rotation method when I build a tree, add several elements, and try to splay the inserted node to the top. Can anyone tell me why I get that error?

Basically, I have this generic SPTNode class with a left pointer, a right pointer, a parent pointer, a root node, and a holder for splayNode. It also has methods for single rotations, ZigZig rotations, ZigZag rotations, splay, and insert methods.

And here is my comparator class:

import java.util.Comparator;


public class SPTNode<AnyType> {

    private SPTNode<AnyType>left;
    private SPTNode<AnyType>right;
    private SPTNode<AnyType>parent;
    private SPTNode<AnyType>root;
    private AnyType value;
    private Comparator<AnyType>cmp;
    private SPTNode<AnyType>splayNode;

    public SPTNode(AnyType data, SPTNode<AnyType> l, SPTNode<AnyType> r, SPTNode<AnyType> p){
        value=data;
        left=l;
        right=r;
        parent=p;
    }

    public SPTNode(AnyType data, Comparator<AnyType>c){
        this(data,null,null,null);
        cmp=c;
    }

    private final int compare(AnyType a, AnyType b){
        return cmp.compare(a,b);
    }

    public final SPTNode<AnyType> singleL(SPTNode<AnyType> n){
        SPTNode<AnyType>newRoot=n.right;
        n.right=newRoot.left;
        newRoot.left=n;
        if(n.parent!=null){
            newRoot.parent=n.parent;
            if(compare(n.value, n.parent.value)<0)
                n.parent.left=newRoot;
            else
                n.parent.right=newRoot;
        }
        n.parent=newRoot;
        if(n.right!=null)
            n.right.parent=n;
        return newRoot;
    }

    public final SPTNode<AnyType>singleR(SPTNode<AnyType>n){
        SPTNode<AnyType>newRoot=n.left;
        n.left=newRoot.right;
        newRoot.right=n;
        if(n.parent!=null){
            newRoot.parent=n.parent;
            if(compare(n.value, n.parent.value)<0)
                n.parent.left=newRoot;
            else
                n.parent.right=newRoot;
        }
        n.parent=newRoot;
        if(n.left!=null)
            n.left.parent=n;
        return newRoot;
    }

    public final SPTNode<AnyType>ZigZigL(SPTNode<AnyType>n){
        n.parent=singleL(n.parent.parent);
        return singleL(n.parent);

    }

    public final SPTNode<AnyType>ZigZigR(SPTNode<AnyType>n){
        n.parent=singleR(n.parent.parent);
        return singleR(n.parent);
    }

    public final SPTNode<AnyType>ZigZagL(SPTNode<AnyType>n){
        return singleL(singleR(n.parent).parent);
    }

    public final SPTNode<AnyType>ZigZagR(SPTNode<AnyType>n){
        return singleR(singleL(n.parent).parent);

    }

    public final SPTNode<AnyType> insert(AnyType value, SPTNode<AnyType> n){
        if(n==null){
            splayNode=new SPTNode<AnyType>(value,cmp);
            return splayNode;
        }
        int compare=compare(value,n.value);
        if(compare<0){
            n.left=insert(value,n.left);
            n.left.parent=n;
        }
        else if(compare>0){
            n.right=insert(value,n.right);
            n.right.parent=n;
        }

        return n;

    }

    public final void insert(AnyType value){
        root=insert(value,root);
        root=splay(splayNode);
    }

    public final SPTNode<AnyType> splay(SPTNode<AnyType> splayNode){
        SPTNode<AnyType>p=splayNode.parent;
        while(p!=null){
            SPTNode<AnyType>gp=p.parent;
            if(gp==null){
                int compare=compare(splayNode.value,p.value);
                if(compare<0)
                    splayNode=singleR(p);
                else
                    splayNode=singleL(p);
            }
            else{
                int compare1=compare(splayNode.value,p.value);
                int compare2=compare(p.value,gp.value);
                if(compare1<0 && compare2<0)
                    splayNode=ZigZigR(splayNode);
                else if(compare1>0 && compare2>0)
                    splayNode=ZigZigL(splayNode);
                else if(compare1<0 && compare2>0)
                    splayNode=ZigZagL(splayNode);
                else
                    splayNode=ZigZagR(splayNode);
            }
            p=splayNode.parent;
        }

        return splayNode;

    }


}

Answer 1

The problem if everything else is same as a binary search tree. When using the parent pointer you need to be careful if,

1) the parent of the node is null then you are at the root area and need to set the root to you new node. Update its parent pointers too.

2) If the parent has a right child and you moved that child as part of the rotation. Set the new node to be the right child. Need to check if the parent's left or right was the case.

3) Need to check for null too when setting parent pointers.

I got a couple of exceptions while using parent pointers and got it corrected here