自底向上展开树时出现空指针异常

Question

我正在尝试在java中做一个自下而上的展开树。但是，当我构建一个树，添加几个元素，并尝试将插入的节点显示到顶部时，我将在旋转方法中得到一个空指针异常。有人能告诉我为什么会出现这个错误吗?

基本上，我有这个通用的SPTNode类，它有一个左指针、一个右指针、一个父指针、一个根节点和一个spplaynode的持有者。它还有单个旋转、之字形旋转、之字形旋转、显示和插入方法。

这是我的比较器类

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

如果其他都和二叉搜索树一样，问题就来了。当使用父指针时，你需要小心，如果

1)节点的父节点为空，那么您在根区域，需要将根设置为您的新节点。也要更新父指针。

2)如果父元素有右子元素，并且你移动了该子元素作为旋转的一部分。将新节点设置为正确的子节点。需要检查父母的左边还是右边。

3)设置父指针时也需要检查null

我在使用父指针时遇到了一些异常，并在这里得到了纠正